Crossing Minimization for Symmetries

Buchheim, Christoph and Hong, Seok-Hee (2005) Crossing Minimization for Symmetries. [Journal (Paginated)]

This is the latest version of this item.

Full text not available from this repository.


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(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.

Item Type: Journal (Paginated)
Additional Information: 10.1007/s00224-005-1142-5
Classifications: G Algorithms and Complexity > G.910 Symmetries
G Algorithms and Complexity > G.420 Crossings
P Styles > P.780 Symmetric

Available Versions of this Item

Actions (login required)

View Item View Item