
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.
ddc:510, Computational Geometry (cs.CG), FOS: Computer and information sciences, Extremal problems in graph theory, I.3.5, Graph representations (geometric and intersection representations, etc.), G.2.1, G.2.2, 510, graph drawing, G.2.1; G.2.2; I.3.5, 68R10, 68U05, Computer Science - Computational Geometry, Mathematics, info:eu-repo/classification/ddc/510
ddc:510, Computational Geometry (cs.CG), FOS: Computer and information sciences, Extremal problems in graph theory, I.3.5, Graph representations (geometric and intersection representations, etc.), G.2.1, G.2.2, 510, graph drawing, G.2.1; G.2.2; I.3.5, 68R10, 68U05, Computer Science - Computational Geometry, Mathematics, info:eu-repo/classification/ddc/510
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
