Crossing Minimization for Symmetries

Buchheim, Christoph and Hong, Seok-Hee (2002) Crossing Minimization for Symmetries. In: 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), November 20-23, 2002 , pp. 563-574(Official URL: http://dx.doi.org/10.1007/3-540-36136-7_49).

WarningThere is a more recent version of this item available.
Full text not available from this repository.

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36136-7_49
Classifications: G Algorithms and Complexity > G.910 Symmetries
G Algorithms and Complexity > G.420 Crossings
P Styles > P.780 Symmetric
URI: http://gdea.informatik.uni-koeln.de/id/eprint/534

Available Versions of this Item

Actions (login required)

View Item View Item