pith. machine review for the scientific record. sign in

arxiv: 2605.00603 · v1 · submitted 2026-05-01 · 💻 cs.CG · cs.DS

Recognition: unknown

Upward-Planar Drawings with Bounded Span

Patrizio Angelini , Sabine Cornelsen , Giordano Da Lozzo , Fabrizio Frati , Philipp Kindermann , Ignaz Rutter , Johannes Zink
Authors on Pith no claims yet

Pith reviewed 2026-05-09 15:05 UTC · model grok-4.3

classification 💻 cs.CG cs.DS
keywords upward-planar drawingsNP-completenessdirected treesst-planar graphsfixed-parameter tractabilitylayered drawingsgraph drawingspan minimization
0
0 comments X

The pith

Determining the minimum span of upward-planar drawings is NP-complete for directed trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that finding the smallest possible maximum edge span in an integer-y upward-planar drawing of a directed graph is NP-complete, even when restricted to directed trees or biconnected single-source graphs. This computational hardness result applies to the problem of creating compact, crossing-free visualizations where all edges point strictly upward with minimal height differences. In contrast, polynomial-time algorithms exist for families with a bounded number of sources, such as st-planar graphs and graphs with a prescribed planar or upward-planar embedding. The authors also derive combinatorial bounds on the span for trees and demonstrate fixed-parameter tractability when parameterized by vertex cover size or by treedepth together with the target span.

Core claim

An upward-planar drawing uses y-monotone upward edges and integer y-coordinates for vertices; the span of such a drawing is the largest |y-difference| over its edges, and the span of the graph is the minimum such value over all possible drawings. The central discovery is that computing this graph span is NP-complete for directed trees and for biconnected single-source graphs, while it admits efficient algorithms for several restricted classes including those with a constant number of sources and st-planar graphs.

What carries the argument

The span, defined as the min-max y-difference in upward-planar integer drawings, with NP-completeness shown via reductions from known hard problems and tractability via dynamic programming over bounded sources or embeddings.

Load-bearing premise

The graphs under consideration admit at least one upward-planar drawing, and the drawings are restricted to those with integer y-coordinates for vertices.

What would settle it

A specific directed tree instance where an efficient algorithm claims a span of 2, but exhaustive enumeration of possible y-coordinate assignments shows that all upward-planar drawings require a maximum edge span of at least 3.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies the span of upward-planar drawings of directed graphs, defined as the minimum, over all upward-planar drawings with integer y-coordinates, of the maximum |y(u)-y(v)| over edges. It establishes combinatorial upper and lower bounds on the span of directed trees, proves NP-completeness of computing the span for directed trees and for biconnected single-source graphs, and gives polynomial-time algorithms for st-planar graphs, for graphs with a prescribed planar or upward-planar embedding, and FPT algorithms parameterized by vertex cover or by treedepth plus span.

Significance. If the proofs are correct, the work provides the first complexity classification for span minimization in upward-planar drawings and demonstrates that the problem remains hard even on trees. The positive results for bounded-source families and the FPT algorithms are of practical interest for graph-drawing applications. The combinatorial bounds on trees add theoretical value and connect to existing literature on layered and upward drawings.

minor comments (3)
  1. The abstract states that 'efficient algorithms' are given for several families; replacing this with explicit running times (e.g., linear-time for st-planar graphs) would improve precision.
  2. A summary table collecting the complexity status (NP-complete vs. polynomial vs. FPT) for each graph class considered would help readers navigate the results.
  3. In the preliminaries, the distinction between the span of a drawing and the span of a graph could be emphasized with a short example immediately after the definitions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of our results, and the recommendation for minor revision. The significance statement correctly highlights the complexity classification and practical aspects of our work. Since the report lists no specific major comments, we have no point-by-point rebuttals to provide. We will incorporate any minor suggestions (e.g., clarifications or polishing) in the revised version.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper's core results consist of NP-completeness proofs for span minimization on directed trees and biconnected single-source graphs, together with polynomial-time algorithms for st-planar graphs and prescribed embeddings. These rest on standard combinatorial definitions of upward-planar drawings with integer y-coordinates and edge span as max |y(u)-y(v)|, plus conventional reductions from known NP-complete problems. No equation or claim reduces by construction to a fitted parameter, self-citation chain, or renamed input; the combinatorial bounds and complexity separations are independent of the paper's own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on standard definitions of upward-planar drawings and integer y-coordinates from prior graph-drawing literature, plus standard complexity assumptions; no new free parameters or invented entities are introduced.

axioms (2)
  • domain assumption Directed graphs under consideration admit at least one upward-planar drawing with integer y-coordinates.
    Required for the span to be well-defined and finite.
  • standard math Standard assumptions of computational complexity theory, including that NP-completeness reductions are polynomial-time computable.
    Invoked when claiming NP-completeness for trees and single-source graphs.

pith-pipeline@v0.9.0 · 5534 in / 1323 out tokens · 65493 ms · 2026-05-09T15:05:02.702976+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    A review on brain tumor segmentation based on deep learning methods with federated learning techniques

    1 Patrizio Angelini, Pier Francesco Cortese, Giuseppe Di Battista, and Maurizio Patrignani. Topological morphing of planar graphs.Theor. Comput. Sci., 514:2–20, 2013.doi:10.1016/J. TCS.2013.08.018. 2 Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, and Fabrizio Frati. Strip planarity testing for embedded planar graphs.Algorithmica, 77(4):1022–1...

    work page doi:10.1016/j 2013

  2. [2]

    8 Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, and Roberto Tamassia

    To appear.arXiv:2409.01889. 8 Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, and Roberto Tamassia. Optimal upward planarity testing of single-source digraphs.SIAM J. Comput., 27(1):132–169,

    work page arXiv

  3. [3]

    9 Václav Blazej, Jirí Fiala, and Giuseppe Liotta

    doi:10.1137/S0097539794279626. 9 Václav Blazej, Jirí Fiala, and Giuseppe Liotta. On edge-length ratios of partial 2-trees.Int. J. Comput. Geom. Appl., 31(2-3):141–162, 2021.doi:10.1142/S0218195921500072. 10 Václav Blazej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. Constrained and ordered level planarity parameterize...

    work page doi:10.1137/s0097539794279626 2021

  4. [4]

    12 Guido Brückner and Ignaz Rutter

    URL:https://doi.org/10.20382/jocg.v11i1a6, doi:10.20382/JOCG.V11I1A6. 12 Guido Brückner and Ignaz Rutter. Partial and constrained level planarity.Theor. Comput. Sci., 1045:115291, 2025.doi:10.1016/J.TCS.2025.115291. 13 Timothy M. Chan. A near-linear area bound for drawing binary trees.Algorithmica, 34(1):1–13, 2002.doi:10.1007/S00453-002-0937-X. 14 Giorda...

    work page doi:10.20382/jocg.v11i1a6 2025

  5. [5]

    Hierarchies and planarity theory.IEEE Trans

    16 Giuseppe Di Battista and Enrico Nardelli. Hierarchies and planarity theory.IEEE Trans. Syst. Man Cybern., 18(6):1035–1046, 1988.doi:10.1109/21.23105. 17 Giuseppe Di Battista and Roberto Tamassia. Algorithms for plane representations of acyclic digraphs.Theor. Comput. Sci., 61:175–198, 1988.doi:10.1016/0304-3975(88)90123-5. 18 Giuseppe Di Battista and R...

    work page doi:10.1109/21.23105 1988

  6. [6]

    22 Fabrizio Frati

    doi:10.1007/S00453-004-1144-8. 22 Fabrizio Frati. On minimum area planar upward drawings of directed trees and other families of directed acyclic graphs.Int. J. Comput. Geom. Appl., 18(3):251–271, 2008.doi: 10.1142/S021819590800260X. 23 Fabrizio Frati. Upward planarity testing of biconnected outerplanar DAGs solves partition. Theor. Comput. Sci., 998:1145...

    work page doi:10.1007/s00453-004-1144-8 2008

  7. [7]

    R., Koutsofios, E., North, S

    doi:10.1109/32.221135. 26 Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman,

    work page doi:10.1109/32.221135

  8. [8]

    doi:10.1007/BF01108622. 28 Jr. H. W. Lenstra. Integer programming with a fixed number of variables.Mathematics of Operations Research, 8,

    work page doi:10.1007/bf01108622

  9. [9]

    30 Lenwood S

    doi:10.1016/0020-0190(81)90120-4. 30 Lenwood S. Heath and Arnold L. Rosenberg. Laying out graphs using queues.SIAM J. Comput., 21(5):927–958, 1992.doi:10.1137/0221055. 31 Monika Rauch Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. Faster shortest-path algorithms for planar graphs.J. Comput. Syst. Sci., 55(1):3–23,

    work page doi:10.1016/0020-0190(81)90120-4 1992

  10. [10]

    32 Michael D

    doi: 10.1006/JCSS.1997.1493. 32 Michael D. Hutton and Anna Lubiw. Upward planar drawing of single-source acyclic digraphs. SIAM J. Comput., 25(2):291–311, 1996.doi:10.1137/S0097539792235906. 33 Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montec- chiani, and Kirill Simonov. Upward and orthogonal planarity are W[1]-hard...

    work page doi:10.1006/jcss.1997.1493 1997

  11. [11]

    Ordered level planarity and its relationship to geodesic planarity, bi-monotonicity, and variations of level planarity.ACM Trans

    36 Boris Klemz and Günter Rote. Ordered level planarity and its relationship to geodesic planarity, bi-monotonicity, and variations of level planarity.ACM Trans. Algorithms, 15(4):53:1–53:25, 2019.doi:10.1145/3359587. 37 Kurt Mehlhorn.Data Structures and Algorithms: Multi-dimensional Searching and Computa- tional Geometry, volume

    work page doi:10.1145/3359587 2019

  12. [12]

    Monotone drawings of planar graphs.J

    38 János Pach and Géza Tóth. Monotone drawings of planar graphs.J. Graph Theory, 46(1):39–47, 2004.doi:10.1002/JGT.10168. P. Angelini, S. Cornelsen, G. Da Lozzo, F. Frati, P. Kindermann, I. Rutter, J. Zink 35 39 Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. Methods for visual understanding of hierarchical system structures.IEEE Transactions on System...

    work page doi:10.1002/jgt.10168 2004