Crossing Minimization for Symmetries (Journal Version)

Buchheim, Christoph and Hong, Seok-Hee (2005) Crossing Minimization for Symmetries (Journal Version).
Published in: Theory of Computing Systems Vol. 38 (3). pp. 293-311.


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.

Full text not available from this repository. (Request a copy)
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2005-484
Depositing User: Christoph Buchheim
Date Deposited: 03 Jun 2005 00:00
Last Modified: 12 Jan 2012 10:26