DROPS

Document

DOI: 10.4230/LIPIcs.GD.2024.33

Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach

Authors: Markus Chimani, Torben Donzelmann, Nick Kloster, Melissa Koch, Jan-Jakob Völlering, and Mirko H. Wagner

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

Abstract

Beyond planarity concepts (prominent examples include k-planarity or fan-planarity) apply certain restrictions on the allowed patterns of crossings in drawings. It is natural to ask, how much the number of crossings may increase over the traditional (unrestricted) crossing number. Previous approaches to bound such ratios, e.g. [Markus Chimani et al., 2022; Nathan van Beusekom et al., 2022], require very specialized constructions and arguments for each considered beyond planarity concept, and mostly only yield asymptotically non-tight bounds. We propose a very general proof framework that allows us to obtain asymptotically tight bounds, and where the concept-specific parts of the proof typically boil down to a couple of lines. We show the strength of our approach by giving improved or first bounds for several beyond planarity concepts.

Cite as

Markus Chimani, Torben Donzelmann, Nick Kloster, Melissa Koch, Jan-Jakob Völlering, and Mirko H. Wagner. Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.GD.2024.33,
  author =	{Chimani, Markus and Donzelmann, Torben and Kloster, Nick and Koch, Melissa and V\"{o}llering, Jan-Jakob and Wagner, Mirko H.},
  title =	{{Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{33:1--33:17},
  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.33},
  URN =		{urn:nbn:de:0030-drops-213175},
  doi =		{10.4230/LIPIcs.GD.2024.33},
  annote =	{Keywords: Beyond planarity, crossing number, crossing ratio, proof framework}
}

Search Results

Documents authored by Koch, Melissa

Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach

Abstract

Cite as

Thanks for your feedback!

Could not send message