Crossing Number of 3-Plane Drawings
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916649772253184 |
|---|---|
| author | Goetze, Miriam Hoffmann, Michael Rutter, Ignaz Ueckerdt, Torsten |
| author_facet | Goetze, Miriam Hoffmann, Michael Rutter, Ignaz Ueckerdt, Torsten |
| contents | We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs (KKKRSU GD 2024) can be used to count the crossings in terms of the number $n$ of vertices. As a main result, we show that every 3-plane drawing has at most $5.5(n-2)$ crossings, which is tight. In particular, it follows that every 3-planar graph on $n$ vertices has crossing number at most $5.5n$, which improves upon a recent bound (BBBDHKMOW GD 2024) of $6.6n$. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most $5.5(n-2)$ edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_08365 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Crossing Number of 3-Plane Drawings Goetze, Miriam Hoffmann, Michael Rutter, Ignaz Ueckerdt, Torsten Combinatorics Computational Geometry We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs (KKKRSU GD 2024) can be used to count the crossings in terms of the number $n$ of vertices. As a main result, we show that every 3-plane drawing has at most $5.5(n-2)$ crossings, which is tight. In particular, it follows that every 3-planar graph on $n$ vertices has crossing number at most $5.5n$, which improves upon a recent bound (BBBDHKMOW GD 2024) of $6.6n$. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most $5.5(n-2)$ edges. |
| title | Crossing Number of 3-Plane Drawings |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2503.08365 |