Upward-Planar Drawings with Bounded Span
This work addresses the computational complexity and algorithmic aspects of minimizing edge span in upward-planar drawings, a problem relevant to graph drawing and visualization.
The paper studies the span of upward-planar drawings of directed graphs, providing upper and lower bounds for directed trees and proving NP-completeness for trees and biconnected single-source graphs. It also gives efficient algorithms for families with bounded sources and shows fixed-parameter tractability for vertex cover number and treedepth plus span.
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.