Abstract
Research about crossings is typically about minimization. In this pa- per, 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 approx- imation even for the unweighted geometric case. We also prove that the unweighted topological case is NP-hard.
Original language | English (US) |
---|---|
Pages (from-to) | 67-87 |
Number of pages | 21 |
Journal | Journal of Graph Algorithms and Applications |
Volume | 22 |
Issue number | 1 |
DOIs | |
State | Published - Jan 1 2018 |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
- Computer Science Applications
- Geometry and Topology
- Computational Theory and Mathematics