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.

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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (462kB) | Preview
Download: [img] PDF - Preprinted Version
Download (306kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Christoph Buchheim
Date Deposited: 23 Nov 2007 00:00
Last Modified: 12 Jan 2012 11:51
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/440