Monotone Arc Diagrams with few Biarcs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910576588881920 |
|---|---|
| author | Chaplick, Steven Förster, Henry Hoffmann, Michael Kaufmann, Michael |
| author_facet | Chaplick, Steven Förster, Henry Hoffmann, Michael Kaufmann, Michael |
| contents | We show that every planar graph has a monotone topological 2-page book embedding where at most (4n-10)/5 (of potentially 3n-6) edges cross the spine, and every edge crosses the spine at most once; such an edge is called a biarc. We can also guarantee that all edges that cross the spine cross it in the same direction (e.g., from bottom to top). For planar 3-trees we can further improve the bound to (3n-9)/4, and for so-called Kleetopes we obtain a bound of at most (n-8)/3 edges that cross the spine. The bound for Kleetopes is tight, even if the drawing is not required to be monotone. A Kleetope is a plane triangulation that is derived from another plane triangulation T by inserting a new vertex v_f into each face f of T and then connecting v_f to the three vertices of f. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_14299 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Monotone Arc Diagrams with few Biarcs Chaplick, Steven Förster, Henry Hoffmann, Michael Kaufmann, Michael Discrete Mathematics Computational Geometry Combinatorics 68R10 (Primary) 05C10, 05C62 (Secondary) F.2.2; G.2.1 We show that every planar graph has a monotone topological 2-page book embedding where at most (4n-10)/5 (of potentially 3n-6) edges cross the spine, and every edge crosses the spine at most once; such an edge is called a biarc. We can also guarantee that all edges that cross the spine cross it in the same direction (e.g., from bottom to top). For planar 3-trees we can further improve the bound to (3n-9)/4, and for so-called Kleetopes we obtain a bound of at most (n-8)/3 edges that cross the spine. The bound for Kleetopes is tight, even if the drawing is not required to be monotone. A Kleetope is a plane triangulation that is derived from another plane triangulation T by inserting a new vertex v_f into each face f of T and then connecting v_f to the three vertices of f. |
| title | Monotone Arc Diagrams with few Biarcs |
| topic | Discrete Mathematics Computational Geometry Combinatorics 68R10 (Primary) 05C10, 05C62 (Secondary) F.2.2; G.2.1 |
| url | https://arxiv.org/abs/2408.14299 |