On the Maximum Crossing Number

DOI10.7155/JGAA.00458zbMATH Open1377.05122arXiv1705.05176OpenAlexW2952582998MaRDI QIDQ4600737FDOQ4600737

Authors: Markus Chimani, Stefan Felsner, Stephen G. Kobourov, Torsten Ueckerdt, Pavel Valtr, Alexander Wolff 

Publication date: 12 January 2018

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Abstract: Research about crossings is typically about minimization. In this paper, we consider emph{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 emph{convex} straight-line drawing, e.g., 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. 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 and prove that the unweighted topological case is NP-hard.

Full work available at URL: https://arxiv.org/abs/1705.05176

Recommendations

• On the maximum crossing number
• An optimality criterion for the crossing number
• Approximating the maximum rectilinear crossing number
• scientific article; zbMATH DE number 5019924
• Improved upper bounds on the crossing number
• The maximum crossing number of the Petersen graph
• scientific article; zbMATH DE number 1047749
• scientific article; zbMATH DE number 4094839
• Maximum cut parameterized by crossing number
• New bounds on crossing numbers

zbMATH Keywords

graph drawing

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (9)

• On the maximum crossing number
• The Bundled Crossing Number
• Bounds of the sum of edge lengths in linear arrangements of trees
• Edge crossings in random linear arrangements
• Approximating the maximum rectilinear crossing number
• Maximum rectilinear crossing number of uniform hypergraphs
• Title not available (Why is that?)
• Many touchings force many crossings
• On the number of maximum intervals

This page was built for publication: On the Maximum Crossing Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4600737)