Upward Book Embeddings of Partitioned Digraphs
This solves an open complexity gap in graph theory for partitioned digraph embeddings, with implications for computational geometry and graph drawing.
The paper tackles the problem of testing upward book embeddings for partitioned digraphs with k=2, showing it is NP-complete, and provides efficient algorithms for specific cases like planar embeddings in O(n log^3 n) time and biconnected directed partial 2-trees in cubic time.
In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph $G=(V,\bigcup^k_{i=1} E_i)$, that is, a digraph whose edge set is partitioned into $k$ subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for $k=1$ and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for $k\geq 3$. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case $k=2$. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when $k=2$, thus closing the complexity gap for the problem. Second, we show that, for an $n$-vertex partitioned digraph $G$ with a prescribed planar embedding, the existence of an upward book embedding of $G$ that respects the given planar embedding can be tested in $O(n \log^3 n)$ time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial $2$-trees.