(Left) An embedding-preserving HP-completion (red) of $G$ (black). (Right) An embedding-preserving 2UBE of $G$ corresponding to (left)
Abstract
We study k-page upward book embeddings ($k$UBEs) of $st$-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on $k$ pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a $k$UBE is NP-complete for $k\geq 3$. A hardness result for this problem was previously known only for $k = 6$ [Heath and Pemmaraju, 1999].
Motivated by this negative result, we focus our attention on $k=2$. On the algorithmic side, we present polynomial-time algorithms for testing the existence of $2$UBEs of planar $st$-graphs with branchwidth $\beta$ and of plane $st$-graphs whose faces have a special structure. These algorithms run in $O(f(\beta)\cdot n+n^3)$ time and $O(n)$ time, respectively, where $f$ is a singly-exponential function on $\beta$. Moreover, on the combinatorial side, we present two notable families of plane $st$-graphs that always admit an embedding-preserving $2$UBE.