On the Maximum Crossing Number

Authors

  • Markus Chimani
  • Stefan Felsner
  • Stephen Kobourov
  • Torsten Ueckerdt
  • Pavel Valtr
  • Alexander Wolff

DOI:

https://doi.org/10.7155/jgaa.00458

Keywords:

graph drawing , maximum crossing number , maximum rectilinear crossing number , maximum convex crossing number , NP-hard , APX-hard

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.

Downloads

Download data is not yet available.

Downloads

Published

2018-01-01

How to Cite

Chimani, M., Felsner, S., Kobourov, S., Ueckerdt, T., Valtr, P., & Wolff, A. (2018). On the Maximum Crossing Number. Journal of Graph Algorithms and Applications, 22(1), 67–87. https://doi.org/10.7155/jgaa.00458