Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929485826228224 |
|---|---|
| author | Chimani, Markus Donzelmann, Torben Kloster, Nick Koch, Melissa Völlering, Jan-Jakob Wagner, Mirko H. |
| author_facet | Chimani, Markus Donzelmann, Torben Kloster, Nick Koch, Melissa Völlering, Jan-Jakob Wagner, Mirko H. |
| contents | 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. [arXiv:1908.03153, arXiv:2105.12452], 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05057 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach Chimani, Markus Donzelmann, Torben Kloster, Nick Koch, Melissa Völlering, Jan-Jakob Wagner, Mirko H. Computational Geometry Discrete Mathematics 68R10, 05C62 G.2.2 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. [arXiv:1908.03153, arXiv:2105.12452], 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. |
| title | Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach |
| topic | Computational Geometry Discrete Mathematics 68R10, 05C62 G.2.2 |
| url | https://arxiv.org/abs/2407.05057 |