×

On the maximum crossing number. (English) Zbl 1508.68262

Brankovic, Ljiljana (ed.) et al., Combinatorial algorithms. 28th international workshop, IWOCA 2017, Newcastle, NSW, Australia, July 17–21, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10765, 61-74 (2018).
Summary: 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. M. Alpert et al. [Electron. J. Comb. 16, No. 1, Research Paper R54, 16 p. (2009; Zbl 1179.05054)] 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 allows a non-convex drawing with more crossings than any convex one. S. Bald et al. [Lect. Notes Comput. Sci. 9797, 455–467 (2016; Zbl 1476.68190)] 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 and prove that the unweighted topological case is NP-hard.
For the entire collection see [Zbl 1386.68003].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI