Academic Journal
The Density Formula: One Lemma to Bound Them All
| العنوان: | The Density Formula: One Lemma to Bound Them All |
|---|---|
| المؤلفون: | Kaufmann, Michael, Klemz, Boris, Knorr, Kristin, M. Reddy, Meghana, Schröder, Felix, Ueckerdt, Torsten |
| المساهمون: | Michael Kaufmann and Boris Klemz and Kristin Knorr and Meghana M. Reddy and Felix Schröder and Torsten Ueckerdt |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| سنة النشر: | 2024 |
| المجموعة: | DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| مصطلحات موضوعية: | beyond-planar, density, fan-planar, fan-crossing, right-angle crossing, quasiplanar |
| الوصف: | 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. |
| نوع الوثيقة: | article in journal/newspaper conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.7 |
| DOI: | 10.4230/LIPIcs.GD.2024.7 |
| الاتاحة: | https://doi.org/10.4230/LIPIcs.GD.2024.7 https://nbn-resolving.org/urn:nbn:de:0030-drops-212913 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.7 |
| Rights: | https://creativecommons.org/licenses/by/4.0/legalcode |
| رقم الانضمام: | edsbas.45F8EA8 |
| قاعدة البيانات: | BASE |
| DOI: | 10.4230/LIPIcs.GD.2024.7 |
|---|