Simplifying Non-Simple Fan-Planar Drawings
| Autor: | Boris Klemz, Kristin Knorr, Meghana M. Reddy, Felix Schröder |
|---|---|
| Přispěvatelé: | Purchase, Helen C., Rutter, Ignaz |
| Rok vydání: | 2023 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Computational Theory and Mathematics General Computer Science I.3.5 Simple topological graphs Fan-planar graphs Beyond-planar graphs Graph drawing Computer Science - Computational Geometry F.2.2 Geometry and Topology Computer Science Applications Theoretical Computer Science |
| Zdroj: | Lecture Notes in Computer Science, 12868 Graph Drawing and Network Visualization Lecture Notes in Computer Science ISBN: 9783030929305 |
| ISSN: | 1526-1719 |
| DOI: | 10.7155/jgaa.00618 |
| Popis: | A drawing of a graph is fan-planar if the edges intersecting a common edge $a$ share a vertex $A$ on the same side of $a$. More precisely, orienting $e$ arbitrarily and the other edges towards $A$ results in a consistent orientation of the crossings. So far, fan-planar drawings have only been considered in the context of simple drawings, where any two edges share at most one point, including endpoints. We show that every non-simple fan-planar drawing can be redrawn as a simple fan-planar drawing of the same graph while not introducing additional crossings. Combined with previous results on fan-planar drawings, this yields that $n$-vertex-graphs having such a drawing can have at most $6.5n$ edges and that the recognition of such graphs is NP-hard. We thereby answer an open problem posed by Kaufmann and Ueckerdt in 2014. Comment: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|