Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Graph Drawing Beyond Planarity
DOI: 10.7155/jgaa.00458
On the Maximum Crossing Number
Markus Chimani,
Stefan Felsner,
Stephen Kobourov,
Torsten Ueckerdt,
Pavel Valtr, and
Alexander Wolff
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.
|
Journal Supporters
|