The Density Formula : One Lemma to Bound Them All
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10490809" target="_blank" >RIV/00216208:11320/24:10490809 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.GD.2024.7" target="_blank" >https://doi.org/10.4230/LIPIcs.GD.2024.7</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.GD.2024.7" target="_blank" >10.4230/LIPIcs.GD.2024.7</a>
Alternative languages
Result language
angličtina
Original language name
The Density Formula : One Lemma to Bound Them All
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GX23-04949X" target="_blank" >GX23-04949X: Fundamental questions of discrete geometry</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Leibniz International Proceedings in Informatics
ISBN
978-3-95977-343-0
ISSN
1868-8969
e-ISSN
—
Number of pages
17
Pages from-to
1-17
Publisher name
Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
Place of publication
Dagstuhl, Germany
Event location
Technische Universität Wien
Event date
Sep 18, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—