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.
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.