2026-08-09T02:33:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21321 2024-10-28T09:51:06Z ddc:004 open_access

Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor Dujmović, Vida La Rose, Camille (rectilinear) crossing number graph minors maximum degree clique-sums The rectilinear crossing number of G is the minimum number of crossings in a straight-line drawing of G. A single-crossing graph is a graph whose crossing number is at most one. We prove that every n-vertex graph G that excludes a single-crossing graph as a minor has rectilinear crossing number O(Δ n), where Δ is the maximum degree of G. This dependence on n and Δ is best possible. The result applies, for example, to K₅-minor-free graphs, and bounded treewidth graphs. Prior to our work, the only bounded degree minor-closed families known to have linear rectilinear crossing number were bounded degree graphs of bounded treewidth as well as bounded degree K_{3,3}-minor-free graphs. In the case of bounded treewidth graphs, our O(Δ n) result is again tight and it improves on the previous best known bound of O(Δ² n) by Wood and Telle, 2007. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vida Dujmović and Camille La Rose 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.37 urn:nbn:de:0030-drops-213219 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.37 eng https://creativecommons.org/licenses/by/4.0/legalcode