×

Crossing minimization for symmetries. (English) Zbl 1101.68720

Summary: 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.

MSC:

68R10 Graph theory (including graph drawing) in computer science

Keywords:

edge crossings
Full Text: DOI