On Planar Straight-Line Dominance Drawings
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909945499222016 |
|---|---|
| author | Angelini, Patrizio Bekos, Michael A. Di Battista, Giuseppe Frati, Fabrizio Grilli, Luca Ortali, Giacomo |
| author_facet | Angelini, Patrizio Bekos, Michael A. Di Battista, Giuseppe Frati, Fabrizio Grilli, Luca Ortali, Giacomo |
| contents | We study the following question, which has been considered since the 90's: Does every $st$-planar graph admit a planar straight-line dominance drawing? We show concrete evidence for the difficulty of this question, by proving that, unlike upward planar straight-line drawings, planar straight-line dominance drawings with prescribed $y$-coordinates do not always exist and planar straight-line dominance drawings cannot always be constructed via a contract-draw-expand inductive approach. We also show several classes of $st$-planar graphs that always admit a planar straight-line dominance drawing. These include $st$-planar $3$-trees in which every stacking operation introduces two edges incoming into the new vertex, $st$-planar graphs in which every vertex is adjacent to the sink, $st$-planar graphs in which no face has the left boundary that is a single edge, and $st$-planar graphs that have a leveling with span at most two. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_05225 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Planar Straight-Line Dominance Drawings Angelini, Patrizio Bekos, Michael A. Di Battista, Giuseppe Frati, Fabrizio Grilli, Luca Ortali, Giacomo Computational Geometry Data Structures and Algorithms We study the following question, which has been considered since the 90's: Does every $st$-planar graph admit a planar straight-line dominance drawing? We show concrete evidence for the difficulty of this question, by proving that, unlike upward planar straight-line drawings, planar straight-line dominance drawings with prescribed $y$-coordinates do not always exist and planar straight-line dominance drawings cannot always be constructed via a contract-draw-expand inductive approach. We also show several classes of $st$-planar graphs that always admit a planar straight-line dominance drawing. These include $st$-planar $3$-trees in which every stacking operation introduces two edges incoming into the new vertex, $st$-planar graphs in which every vertex is adjacent to the sink, $st$-planar graphs in which no face has the left boundary that is a single edge, and $st$-planar graphs that have a leveling with span at most two. |
| title | On Planar Straight-Line Dominance Drawings |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.05225 |