Crossing Number of 3-Plane Drawings
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |