Upward-Planar Drawings with Bounded Span
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909008032432128 |
|---|---|
| author | Angelini, Patrizio Cornelsen, Sabine Da Lozzo, Giordano Frati, Fabrizio Kindermann, Philipp Rutter, Ignaz Zink, Johannes |
| author_facet | Angelini, Patrizio Cornelsen, Sabine Da Lozzo, Giordano Frati, Fabrizio Kindermann, Philipp Rutter, Ignaz Zink, Johannes |
| contents | We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head, and the y-coordinates of the vertices are integers. The span of an edge in such a drawing is the absolute difference between the y-coordinates of its endpoints, and the span of the drawing is the maximum span of any edge. The span of an upward-planar graph is the minimum span over all its upward-planar drawings.
We study the problem of determining the span of upward-planar graphs and provide both combinatorial and algorithmic results. On the combinatorial side, we present upper and lower bounds for the span of directed trees. On the algorithmic side, we show that the problem of determining the span of an upward-planar graph is NP-complete already for directed trees and for biconnected single-source graphs. Moreover, we give efficient algorithms for several graph families with a bounded number of sources, including st-planar graphs and graphs where the planar or upward-planar embedding is prescribed. Furthermore, we show that the problem is fixed-parameter tractable with respect to the vertex cover number and the treedepth plus the span. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00603 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Upward-Planar Drawings with Bounded Span Angelini, Patrizio Cornelsen, Sabine Da Lozzo, Giordano Frati, Fabrizio Kindermann, Philipp Rutter, Ignaz Zink, Johannes Computational Geometry Data Structures and Algorithms We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head, and the y-coordinates of the vertices are integers. The span of an edge in such a drawing is the absolute difference between the y-coordinates of its endpoints, and the span of the drawing is the maximum span of any edge. The span of an upward-planar graph is the minimum span over all its upward-planar drawings. We study the problem of determining the span of upward-planar graphs and provide both combinatorial and algorithmic results. On the combinatorial side, we present upper and lower bounds for the span of directed trees. On the algorithmic side, we show that the problem of determining the span of an upward-planar graph is NP-complete already for directed trees and for biconnected single-source graphs. Moreover, we give efficient algorithms for several graph families with a bounded number of sources, including st-planar graphs and graphs where the planar or upward-planar embedding is prescribed. Furthermore, we show that the problem is fixed-parameter tractable with respect to the vertex cover number and the treedepth plus the span. |
| title | Upward-Planar Drawings with Bounded Span |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.00603 |