Special Issue on Graph Drawing Beyond Planarity
On the Maximum Crossing Number
Vol. 22, no. 1, pp. 67-87, 2018. Regular paper.
Abstract Research about crossings is typically about minimization. In this paper, we consider maximizing the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a convex straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that admits a non-convex drawing with more crossings than any convex drawing. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case. We also prove that the unweighted topological case is NP-hard.
Submitted: May 2017.
Reviewed: August 2017.
Revised: October 2017.
Reviewed: December 2017.
Revised: December 2017.
Accepted: December 2017.
Final: December 2017.
Published: January 2018.
article (PDF)