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 $��$ and of plane $st$-graphs whose faces have a special structure. These algorithms run in $O(f(��)\cdot n+n^3)$ time and $O(n)$ time, respectively, where $f$ is a singly-exponential function on $��$. Moreover, on the combinatorial side, we present two notable families of plane $st$-graphs that always admit an embedding-preserving $2$UBE.

Extended version of "Upward Book Embeddings of st-Graphs", to appear in Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019)