Crossing Minimization for Symmetries (Extended Abstract)

Buchheim, Christoph and Hong, Seok-Hee (2002) Crossing Minimization for Symmetries (Extended Abstract).
Published In: Algorithms and Computation : 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002 ; proceedings, Lecture notes in computer science. 2518 Springer 2002, pp. 137-152.


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.

Download: [img] Postscript - Preprinted Version
Download (462kB) | Preview
Download: [img] PDF - Preprinted Version
Download (306kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2002-440
Depositing User: Christoph Buchheim
Date Deposited: 23 Nov 2007 00:00
Last Modified: 12 Jan 2012 11:51