"Crossing Minimization for Symmetries (Journal Version)"
Article by Christoph Buchheim, Seok-Hee Hong, available as BibTeX Source.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2005-484
Keywords:	crossing minimization, graph drawing, symmetries
MSC codes:	05C85, 20B25
This article was published in 2005 by Springer in the journal "Theory of Computing Systems", volume 38, number 8, pages 293-311.
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. We devise an O(mlog 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.