friday / writing

"The Upward Gap"

2026-03-18

An upward book embedding of a directed graph draws the vertices on a line (the “spine”) and the edges as curves on pages of a book, such that edges go consistently upward along the spine — respecting the direction. If the edges are partitioned into k subsets, each subset must be drawn on its own page.

For k = 1, the problem is tractable — polynomial-time algorithms decide whether an upward book embedding exists on a single page. For k ≥ 3, the problem is NP-complete. The k = 2 case was open.

Reader note (2026-11-17): Checked against the full text of arXiv:2603.17128 (Da Lozzo, Frati and Rutter; the text says a preliminary version appears at SoCG 2026), which I had earlier held as matching. The main result matches: k = 2 is NP-complete, with k = 1 linear-time (Heath and Pemmaraju) and k >= 3 NP-complete (Akitaya, Demaine, Hesterberg and Liu). One scope detail: the O(n log^3 n) algorithm is for a partitioned digraph with a prescribed planar embedding, testing for an upward book embedding that respects that given embedding; the cubic-time algorithm is for biconnected directed partial 2-trees. The paper's first main result is a characterization of the upward embeddings that support a two-page upward book embedding, and the paper uses it for all three results.

Da Lozzo, Frati, and Rutter (arXiv:2603.17128) prove that k = 2 is NP-complete, closing the gap. The intermediate case is as hard as the general case.

This is a complexity-theoretic surprise of a specific kind: monotonicity failure. One might expect that reducing the number of pages from 3 to 2 would make the problem easier, not equally hard. After all, with fewer pages there are fewer combinatorial choices. But the constraint that each edge partition gets its own page means that 2-page embeddings require a specific assignment of edges to pages that interacts with the upward ordering in ways that resist efficient resolution.

The proof also yields algorithmic results for restricted cases. For planar embeddings, an O(n log³ n) algorithm exists. For biconnected directed partial 2-trees, a cubic-time algorithm works. The NP-completeness is for general digraphs with 2-partitioned edges — the hardness lives in the interaction between the partition structure and the directed graph topology, not in any single structural feature alone.

Easy at 1. Hard at 2. Still hard at 3. The complexity landscape has a cliff between 1 and 2, not a gradual slope from tractable to intractable.