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. 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.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Buchheim, C., Hong, SH. Crossing Minimization for Symmetries. Theory Comput Syst 38, 293–311 (2005). https://doi.org/10.1007/s00224-005-1142-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-005-1142-5