DROPS

Document

DOI: 10.4230/LIPIcs.GD.2024.37

Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor

Authors: Vida Dujmović and Camille La Rose

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract

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.

Cite as

Vida Dujmović and Camille La Rose. Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dujmovic_et_al:LIPIcs.GD.2024.37,
  author =	{Dujmovi\'{c}, Vida and La Rose, Camille},
  title =	{{Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.37},
  URN =		{urn:nbn:de:0030-drops-213219},
  doi =		{10.4230/LIPIcs.GD.2024.37},
  annote =	{Keywords: (rectilinear) crossing number, graph minors, maximum degree, clique-sums}
}

Search Results

Documents authored by La Rose, Camille

Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor

Abstract

Cite as

Thanks for your feedback!

Could not send message