"Crossing Minimization for Symmetries (Extended Abstract)"
Article by Christoph Buchheim, Seok-Hee Hong, available as BibTeX Source, postscript file, compressed postscript file and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2002-440
Keywords:	crossing minimization, graph drawing, symmetries
MSC codes:	05C85, 20B25
This article was published in November 2002 by Springer in the proceedings "ISAAC 2002" (edited by Prosenjit Bose and Pat Morin), series "LNCS", volume 2518, pages 563-574.
Abstract:	We consider the problem of drawing a graph with a given symmetry such that the number of edge crossings is minimal. We show that this problem is NP-hard, even if the order of orbits around the rotation center or along the reflection axis is fixed. Nevertheless, there is a linear time algorithm to test planarity and to construct a planar embedding if possible. Finally, we devise an O(m log m) algorithm for computing a crossing minimal drawing if inter-orbit edges may not cross orbits, showing in particular that intra-orbit edges do not contribute to the NP-hardness of the crossing minimization problem for symmetries. From this result, we can derive an O(m log m) crossing minimization algorithm for symmetries with an orbit graph that is a path.