The Density Formula: One Lemma to Bound Them All
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929502496489472 |
|---|---|
| author | Kaufmann, Michael Klemz, Boris Knorr, Kristin Reddy, Meghana M. Schröder, Felix Ueckerdt, Torsten |
| author_facet | Kaufmann, Michael Klemz, Boris Knorr, Kristin Reddy, Meghana M. Schröder, Felix Ueckerdt, Torsten |
| contents | We introduce the Density Formula for (topological) drawings of graphs in the plane or on the sphere, which relates the number of edges, vertices, crossings, and sizes of cells in the drawing. We demonstrate its capability by providing several applications: we prove tight upper bounds on the edge density of various beyond-planar graph classes, including so-called $k$-planar graphs with $k=1,2$, fan-crossing / fan-planar graphs, $k$-bend RAC-graphs with $k=0,1,2$, quasiplanar graphs, and $k^+$-real face graphs. In some cases ($1$-bend and $2$-bend RAC-graphs and fan-crossing / fan-planar graphs), we thereby obtain the first tight upper bounds on the edge density of the respective graph classes. In other cases, we give new streamlined and significantly shorter proofs for bounds that were already known in the literature. Thanks to the Density Formula, all of our proofs are mostly elementary counting and mostly circumvent the typical intricate case analysis found in earlier proofs. Further, in some cases (simple and non-homotopic quasiplanar graphs), our alternative proofs using the Density Formula lead to the first tight lower bound examples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_06193 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Density Formula: One Lemma to Bound Them All Kaufmann, Michael Klemz, Boris Knorr, Kristin Reddy, Meghana M. Schröder, Felix Ueckerdt, Torsten Combinatorics Discrete Mathematics 05C62, 05C10 G.2.2 We introduce the Density Formula for (topological) drawings of graphs in the plane or on the sphere, which relates the number of edges, vertices, crossings, and sizes of cells in the drawing. We demonstrate its capability by providing several applications: we prove tight upper bounds on the edge density of various beyond-planar graph classes, including so-called $k$-planar graphs with $k=1,2$, fan-crossing / fan-planar graphs, $k$-bend RAC-graphs with $k=0,1,2$, quasiplanar graphs, and $k^+$-real face graphs. In some cases ($1$-bend and $2$-bend RAC-graphs and fan-crossing / fan-planar graphs), we thereby obtain the first tight upper bounds on the edge density of the respective graph classes. In other cases, we give new streamlined and significantly shorter proofs for bounds that were already known in the literature. Thanks to the Density Formula, all of our proofs are mostly elementary counting and mostly circumvent the typical intricate case analysis found in earlier proofs. Further, in some cases (simple and non-homotopic quasiplanar graphs), our alternative proofs using the Density Formula lead to the first tight lower bound examples. |
| title | The Density Formula: One Lemma to Bound Them All |
| topic | Combinatorics Discrete Mathematics 05C62, 05C10 G.2.2 |
| url | https://arxiv.org/abs/2311.06193 |