Crossing Minimization for SymmetriesBuchheim, 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. AbstractWe 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.
Available Versions of this Item
Repository Staff Only: item control page References |