Chimani, Markus; Felsner, Stefan; Kobourov, Stephen; Ueckerdt, Torsten; Valtr, Pavel; Wolff, Alexander 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]. Cited in 1 Document 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 Citations:Zbl 1179.05054; Zbl 1476.68190 PDFBibTeX XMLCite \textit{M. Chimani} et al., Lect. Notes Comput. Sci. 10765, 61--74 (2018; Zbl 1508.68262) Full Text: DOI