Upward Book Embeddings of Partitioned Digraphs

Book embeddings are a classic and influential topic in combinatorial and algorithmic graph theory. The notion of a book as a topological space was introduced in the late 60s by Persinger [48] and Atneosen [5], and later developed in its current and more popular form by the seminal work of Ollmann [47]. In a book embedding of a graph $G=(V,E)$, all vertices lie along a line – referred to as the spine – while edges are placed into distinct half-planes bounded by the spine, known as the pages of the book. Therefore, constructing such an embedding for $G$ amounts to computing a pair $(\pi ,\sigma )$, where $\pi :V\leftrightarrow \{1,\mathrm{\dots },|V|\}$ is a linear ordering of the vertices and $\sigma :E\to \{1,\mathrm{\dots },k\}$ is a partition of the edges into $k$ pages so that no two edges in the same page cross according to $\pi$, i.e., their end-vertices do not alternate in $\pi$; see Fig. 1(a) for an example. The minimum value of $k$ for which this is possible is the book thickness of $G$ (also called stack number or page number).

Research on book embeddings originated from problems in VLSI circuit design [20], and has since found applications in sorting permutations [49, 52], fault-tolerant processing [50], compact graph encodings [40, 46], graph drawing [14, 25, 29, 33], computational origami [1, 45], parallel process scheduling [13], parallel matrix computations [36], and other domains. For a more comprehensive overview of applications, see [28]. The notion of book embedding was extended to digraphs by Heath, Pemmaraju, and Trenk [37] by introducing the natural requirement that in a book embedding $(\pi ,\sigma )$ of a digraph $G$ the ordering $\pi$ must be a topological ordering of $G$; see Figs. 1(b) and 1(c) for an example. Such book embeddings are called upward book embeddings as they are naturally depicted with vertices placed on a vertical line and edges drawn as arcs monotonically increasing in the $y$-direction in their page.

Next, we provide an overview of the major algorithmic results on book embeddings; in the full version [21], we also discuss combinatorial results. Concerning undirected graphs, already in 1979, Bernhart and Kainen [10] showed that the graphs of book thickness $1$ are the outerplanar graphs and that the graphs of book thickness $2$ are the sub-Hamiltonian (planar) graphs. Whereas the former are recognizable in linear time [54], recognizing the latter is $\mathrm{𝖭𝖯}$-complete, even for planar triangulations [55]. Recently, Ganian et al. [31] presented a sub-exponential-time algorithm for testing sub-Hamiltonicity, which is asymptotically tight under ETH. Concerning digraphs, the problem of testing the existence of an upward book embedding in $k$ pages is called Upward Book Embedding. For more than two decades, the only known $\mathrm{𝖭𝖯}$-completeness result for the problem was the one shown by Heath and Pemmaraju [35] when $k=6$. Recently, in two subsequent papers, Binucci et al. [16] and Bekos et al. [8, 9] closed the computational gap by showing $\mathrm{𝖭𝖯}$-completeness for $k\ge 3$ and $k=2$, respectively. These results, together with the linear-time algorithm for $k=1$ [35], completely characterize the complexity of the Upward Book Embedding problem with respect to $k$. For $k=2$, efficient algorithms have been devised for special classes [15, 42, 43].

For basic definitions on graphs and their drawings see [22, 27] or the full version of the paper.

Two planar drawings of a connected digraph are topologically equivalent if they have the same clockwise order of the edges around each vertex and the same clockwise order of the edges along the boundary of the outer face. A planar embedding is a class of topologically equivalent planar drawings. A plane digraph is a planar digraph together with a planar embedding. A planar embedding of a digraph is bimodal if, for every vertex $v$, the edges that have their tail at $v$ are consecutive in the clockwise order of the edges incident to $v$.

In this section we characterize the upward embeddings $(ℰ,\lambda )$ of a partitioned upward plane digraph $G=(V,L\cup R)$ that allow for the construction of an upward book embedding.

For a face $f$ of $ℰ$, let ${ℒ}_f$ (resp. ${ℛ}_f$) be the set of maximal directed paths in the boundary of $f$ that consist of edges with $f$ to their right (resp. to their left). The face $f$ is impossible if it satisfies one of the following two conditions (see Fig. 4(a)):

1. (i)

   ${ℒ}_f$ contains a path ${\mathrm{\ell }}_f$ with the following properties: a) ${\mathrm{\ell }}_f$ consists of edges in $R$; b) the rest of the boundary of $f$ is not a single edge; and c) let $e_f^u$ and $e_f^v$ be the edges of ${\mathrm{\ell }}_f$ incident to the extremes $u$ and $v$ of ${\mathrm{\ell }}_f$, respectively; then the angle in $f$ incident to $u$ and to the right of $e_f^u$ and the angle in $f$ incident to $v$ and to the right of $e_f^v$ are small.

2. (ii)

   ${ℛ}_f$ contains a path $r_f$ with the following properties: a) $r_f$ consists of edges in $L$; b) the rest of the boundary of $f$ is not a single edge; and c) let $e_f^u$ and $e_f^v$ be the edges of $r_f$ incident to the extremes $u$ and $v$ of $r_f$, respectively; then the angle in $f$ incident to $u$ and to the left of $e_f^u$ and the angle in $f$ incident to $v$ and to the left of $e_f^v$ are small.

A good embedding is an upward embedding $(ℰ,\lambda )$ that is 4-modal and that is such that no face of $ℰ$ is impossible. We now prove our characterization.

In this section we study the complexity of testing whether a partitioned digraph $G=(V,L\cup R)$ admits an upward book embedding in two pages. We show that the problem is $\mathrm{𝖭𝖯}$-complete by exploiting Theorem 3 and the $\mathrm{𝖭𝖯}$-hardness of Upward Planarity Testing.

In this section we show how to exploit the characterization of Theorem 3 in order to prove that, for an $n$-vertex partitioned plane digraph $G$ with a given planar embedding $ℰ$, it can be tested in $O(n{\log }^{3}n)$ time whether $G$ admits an upward book embedding respecting $ℰ$. We assume that $G$ is connected and refer to the full version for the case in which it is not.

We review a tool for testing whether $G$ admits an upward planar drawing $\mathrm{\Gamma }$ respecting $ℰ$. By Theorem 1, the bimodality of $ℰ$ is necessary for the existence of $\mathrm{\Gamma }$ and can be tested in $O(n)$ time. Thus, the existence of $\mathrm{\Gamma }$ corresponds to the existence of an upward-consistent angle assignment $\lambda$ for $ℰ$, which can be decided by the following strategy of Bertolazzi et al. [11]. Starting from the plane digraph $G$ with planar embedding $ℰ$, one can construct a planar flow network $𝒩$, as illustrated in Fig. 6, where:

• $\mathbf{■}$

  for each switch $v$ of $G$, the network $𝒩$ contains a source $s_v$ supplying a single unit of flow;

• $\mathbf{■}$

  for each face $f$ of $ℰ$, the network $𝒩$ contains a sink $t_f$ that demands a number of units of flow equal to $n_f/2-1$ or $n_f/2+1$, depending on whether $f$ is an internal face or the outer face of $ℰ$, respectively (where $n_f$ is the number of switch angles incident to $f$);

• $\mathbf{■}$

  for each angle $\alpha$ in $ℰ$ at a switch of $G$, the network $𝒩$ contains a node $w_{\alpha }$; and

• $\mathbf{■}$

  the network $𝒩$ contains an arc from each source $s_v$ to each node $w_{\alpha }$ such that the angle $\alpha$ is incident to $v$ in $ℰ$ and an arc from each node $w_{\alpha }$ to each sink $t_f$ such that the angle $\alpha$ is incident to $f$ in $ℰ$; all such arcs have a capacity of a single unit of flow.

By [11], there exists an upward-consistent angle assignment $\lambda$ for $ℰ$ if and only if $𝒩$ admits a feasible flow whose value is the sum $d_T$ of the demands of the sinks in $𝒩$. Indeed, upward-consistent angle assignments and (integral) feasible flows with value $d_T$ are in bijection. Namely, from an upward-consistent angle assignment $\lambda$, one gets a feasible flow for $𝒩$ with value $d_T$ by assigning flow $1$ only to arcs incident to a node $w_{\alpha }$ where $\alpha$ is assigned a large angle by $\lambda$, and from a feasible flow for $𝒩$ with value $d_T$, one gets an upward-consistent angle assignment $\lambda$ by assigning a large angle to each switch angle $\alpha$ such that the arcs incident to node $w_{\alpha }$ are assigned one unit of flow, and a small angle to all other switch angles. Testing whether $G$ admits an upward planar drawing respecting $ℰ$ then becomes equivalent to testing whether $𝒩$ admits a flow whose value is $d_T$, which can be done in $O(n{\log }^{3}n)$ time [17].

Our idea is to modify $𝒩$ so that there is an upward-consistent angle assignment $\lambda$ for $ℰ$ such that $(ℰ,\lambda )$ is a good embedding if and only if $𝒩$ has a feasible flow whose value is $d_T$. The correspondence is actually stronger: As we show in the full version, the integral feasible flows with value $d_T$ for the modified network are in bijection with the upward-consistent angle assignments $\lambda$ for $ℰ$ such that $(ℰ,\lambda )$ is a good embedding. We show an algorithm, called $𝒩$-modifier, that performs a sequence of modifications to $𝒩$. Along the way, $𝒩$-modifier might stop and conclude that $G$ has no upward book embedding respecting $ℰ$.

The $𝒩$-modifier algorithm. We start by describing the modifications to $𝒩$ to ensure 4-modality. Consider any vertex $v$ of $G$. If $v$ is not a switch, then its 4-modality does not depend on the angle assignment, thus we check whether in $ℰ$, in clockwise order around $v$, we have outgoing left edges, outgoing right edges, incoming right edges, and incoming left edges. If the test is negative, then $G$ admits no upward book embedding respecting $ℰ$. If $v$ is a switch, say a source, then we check whether in $ℰ$ the outgoing left edges are consecutive. If the test is negative, then $G$ admits no upward book embedding respecting $ℰ$. If the test is positive and $v$ has no outgoing left edges or no outgoing right edges, the processing of $v$ is concluded. If the test is positive and $v$ has both outgoing left and outgoing right edges, we modify $𝒩$ as follows; see Fig. 7. Let $e$ be the left edge outgoing from $v$ such that the edge $e^{\prime }$ preceding $e$ in clockwise order around $v$ is a right edge, let $\alpha$ be the angle $(e,e^{\prime })$. For each angle $\beta \ne \alpha$ incident to $v$ in $ℰ$, the algorithm $𝒩$-modifier removes $w_{\beta }$ and its incident arcs from $𝒩$. This forces the arc $(s_v,w_{\alpha })$ to be assigned one unit of flow, hence making $\alpha$ large.

We next describe the modifications $𝒩$-modifier applies to $𝒩$ in order to ensure the absence of impossible faces. Consider any face $f$ of $ℰ$ and any maximal directed path ${\mathrm{\ell }}_f$ in the boundary of $f$ with $f$ to its right (the treatment of the maximal directed paths with $f$ to their left is analogous). If ${\mathrm{\ell }}_f$ contains a left edge or if the rest of the boundary of $f$ is a single edge, then the processing of ${\mathrm{\ell }}_f$ is concluded. Otherwise, let $u$ and $v$ be the extremes of ${\mathrm{\ell }}_f$, let $e_f^u$ and $e_f^v$ be the edges of ${\mathrm{\ell }}_f$ incident to $u$ and $v$, let ${\alpha }_f^u$ be the angle in $f$ incident to $u$ and to the right of $e_f^u$, and let ${\alpha }_f^v$ be the angle in $f$ incident to $v$ and to the right of $e_f^v$. By Theorem 3, at least one of the angles ${\alpha }_f^u$ and ${\alpha }_f^v$ has to be large. By the maximality of ${\mathrm{\ell }}_f$, both ${\alpha }_f^u$ and ${\alpha }_f^v$ are switch angles. We say that ${\alpha }_f^u$ (resp. ${\alpha }_f^v$) is enlargeable if the node $w_{{\alpha }_f^u}$ (resp. the node $w_{{\alpha }_f^v}$) is in $𝒩$. Note that, even if $u$ (resp. $v$) is a switch of $G$, $w_{{\alpha }_f^u}$ (resp. $w_{{\alpha }_f^v}$) might not be in $𝒩$, because of some previous modification of $𝒩$. We distinguish three cases.

• $\mathbf{■}$

  If neither ${\alpha }_f^u$ nor ${\alpha }_f^v$ is enlargeable, then $G$ admits no upward book embedding respecting $ℰ$.

• $\mathbf{■}$

  If just one of ${\alpha }_f^u$ and ${\alpha }_f^v$, say ${\alpha }_f^u$, is enlargeable, we modify $𝒩$ as follows: For each angle $\beta \ne {\alpha }_f^u$ incident to $u$ in $ℰ$, we remove $w_{\beta }$ and its incident arcs from $𝒩$, thus forcing the arc $(s_u,w_{{\alpha }_f^u})$ to be assigned one unit of flow and making ${\alpha }_f^u$ large.

• $\mathbf{■}$

  Finally, suppose that both ${\alpha }_f^u$ and ${\alpha }_f^v$ are enlargeable, as in Fig. 8. If there exists no angle $\beta \ne {\alpha }_f^u$ incident to $u$ whose corresponding node $w_{\beta }$ is in $𝒩$, or no angle $\beta \ne {\alpha }_f^v$ incident to $v$ whose corresponding node $w_{\beta }$ is in $𝒩$, then the processing of ${\mathrm{\ell }}_f$ is concluded, since it is already guaranteed that one of ${\alpha }_f^u$ and ${\alpha }_f^v$ will be a large angle. Otherwise, we add to $𝒩$ a sink $t_f^{uv}$ with demand $1$, as well as arcs $(w_{{\alpha }_f^u},t_f^{uv})$ and $(w_{{\alpha }_f^v},t_f^{uv})$ with capacity $1$, and decrease by $1$ the demand of $t_f$. This forces one of $(w_{{\alpha }_f^u},t_f^{uv})$ and $(w_{{\alpha }_f^v},t_f^{uv})$ (and consequently one of $(s_u,w_{{\alpha }_f^u})$ and $(s_v,w_{{\alpha }_f^v})$) to be assigned one unit of flow, hence making large ${\alpha }_f^u$ or ${\alpha }_f^v$, respectively. Note that $𝒩$ remains a planar flow network.

The described algorithm is the main ingredient for the proof of the following theorem.

In this section we show how to test whether an $n$-vertex biconnected partitioned directed partial $2$-tree $G=(V,L\cup R)$ admits an upward book embedding in two pages. We leverage tools introduced in [18, 19] to efficiently test whether a directed partial $2$-tree is upward planar. Note that, lacking a characterization such as the one in Theorem 3, it would be prohibitive to lift such tools to work for our problem. Let $e^{\ast }$ be an edge of $G$. We test in $O(n^2)$ time whether $G$ admits a good embedding with $e^{\ast }$ on the outer face. Repeating this test for all $O(n)$ choices of $e^{\ast }$ yields an $O(n^3)$-time algorithm to decide whether $G$ admits a good embedding. By Theorem 3, this is equivalent to testing whether $G$ admits an upward book embedding.

Let $T$ be an SPQ-tree of $G$, rooted at the Q-node ${\rho }^{\ast }$ corresponding to $e^{\ast }$. Let $\mu$ be a node of $T$ with poles $u$ and $v$ and with pertinent graph $G_{\mu }$. A $uv$-external good embedding of $G_{\mu }$ is a good embedding of $G_{\mu }$ in which $u$ and $v$ are incident to the outer face. The requirement that $e^{\ast }$ is incident to the outer face of any upward embedding $(ℰ,\lambda )$ of $G$ implies that the restriction of $(ℰ,\lambda )$ to $G_{\mu }$ is indeed a $uv$-external good embedding of $G_{\mu }$.

A $uv$-external good embedding $({ℰ}_{\mu },{\lambda }_{\mu })$ of $G_{\mu }$ can be succinctly represented by a descriptor pair, which consists of a shape descriptor $⟨{\tau }_l,{\tau }_r,{\lambda }^u,{\lambda }^v,{\rho }_l^u,{\rho }_r^u,{\rho }_l^v,{\rho }_r^v⟩$ and of a pbe descriptor (short for partitioned book embedding descriptor) $⟨p_l^u,p_r^u,p_l^v,p_r^v,{\chi }_l,{\chi }_r,{\alpha }_l^u,{\alpha }_r^u,{\alpha }_l^v,{\alpha }_r^v⟩$, with the following meaning. Let the left outer path $P_l$ (resp. the right outer path $P_r$) be the path obtained by traversing the boundary of the outer face $f_{\mu }$ of ${ℰ}_{\mu }$ from $u$ to $v$ in clockwise (resp. counterclockwise) direction. The label ${\tau }_l$ (${\tau }_r$) is the sum of the labels assigned by ${\lambda }_{\mu }$ to the angles in $f_{\mu }$ at the vertices of $P_l$ (resp. $P_r$), excluding $u$ and $v$. The values ${\lambda }^u$ and ${\lambda }^v$ are the labels of the angles at $u$ and $v$ in $f_{\mu }$, respectively. The label ${\rho }_l^u$ is in or out depending on whether the edge of $P_l$ incident to $u$ is incoming or outgoing at $u$, respectively; the values ${\rho }_r^u$, ${\rho }_l^v$, and ${\rho }_r^v$ are defined analogously. The label $p_l^u$ is $L$ or $R$ depending on whether the edge of $P_l$ incident to $u$ belongs to $L$ or $R$, respectively; the values $p_r^u$, $p_l^v$, and $p_r^v$ are defined analogously. The label ${\chi }_l$ is 1 if $P_l$ is a directed path from $u$ to $v$ and all its edges belong to $L$ or if $P_l$ is a directed path from $v$ to $u$ and all its edges belong to $R$, it is 0 otherwise. The label ${\chi }_r$ is defined analogously for $P_r$. The label ${\alpha }_l^u$ is 1 if $P_l$ contains a directed path from $u$ to a vertex $w\notin \{u,v\}$ whose edges belong to $L$ or a directed path from a vertex $w\notin \{u,v\}$ to $u$ whose edges belong to $R$ and if ${\lambda }_{\mu }$ assigns a small angle at $w$ in $f_{\mu }$; the label ${\alpha }_l^u$ is 0 otherwise. The labels ${\alpha }_r^u$, ${\alpha }_l^v$, and ${\alpha }_r^v$ are defined analogously, with respect to $P_r$ rather than $P_l$ and/or with respect to $v$ rather than $u$.

The information in a descriptor pair fully describes how a $uv$-external good embedding of $G_{\mu }$ interfaces with the rest of $G$ for the construction of a good embedding of $G$ with $e^{\ast }$ on the outer face. That is, for a good embedding $(ℰ,\lambda )$ of $G$ with $e^{\ast }$ on the outer face, let $({ℰ}_{\mu },{\lambda }_{\mu })$ be the $uv$-external good embedding of $G_{\mu }$ in $(ℰ,\lambda )$, and let $(\sigma ,\omega )$ be the descriptor pair of $({ℰ}_{\mu },{\lambda }_{\mu })$. Replacing $({ℰ}_{\mu },{\lambda }_{\mu })$ with any other $uv$-external good embedding of $G_{\mu }$ with descriptor pair $(\sigma ,\omega )$ still results in a good embedding of $G$ with $e^{\ast }$ on the outer face. Even more, for a $uv$-external good embedding $({ℰ}_{\mu },{\lambda }_{\mu })$ of $G_{\mu }$ with descriptor pair $(\sigma ,\omega )$, let $\nu$ be a child of $\mu$ with poles $w$ and $z$, and let $({\sigma }^{\prime },{\omega }^{\prime })$ be the descriptor pair of the $wz$-external good embedding $({ℰ}_{\nu },{\lambda }_{\nu })$ of $G_{\nu }$ in $({ℰ}_{\mu },{\lambda }_{\mu })$. Replacing $({ℰ}_{\nu },{\lambda }_{\nu })$ with any other $wz$-external good embedding of $G_{\nu }$ with descriptor pair $({\sigma }^{\prime },{\omega }^{\prime })$ results in a $uv$-external good embedding of $G_{\mu }$ with descriptor pair $(\sigma ,\omega )$. This allows us to only keep track of the descriptor pairs $(\sigma ,\omega )$ that are “realizable” by $G_{\mu }$, rather than of the actual $uv$-external good embeddings of $G_{\mu }$. This is formalized by the notion of feasible set ${ℱ}_{\mathrm{\mu }}$ for $\mu$, which contains all the descriptor pairs $(\sigma ,\omega )$ such that $G_{\mu }$ admits a $uv$-external good embedding with descriptor pair $(\sigma ,\omega )$.

The core of our algorithm consists of a bottom-up computation of the feasible set ${ℱ}_{\mu }$ for each node $\mu$ of $T$. If $\mu$ is a non-root Q-node, then $G_{\mu }$ has a unique $uv$-external good embedding, hence ${ℱ}_{\mu }$ contains a unique descriptor pair and is computed in $O(1)$ time.

If $\mu$ is an S-node, let ${\nu }_1$ and ${\nu }_2$ be the children of $\mu$ in $T$ and let $w$ be the unique vertex shared by $G_{{\nu }_1}$ and $G_{{\nu }_2}$. We combine every descriptor pair $({\sigma }_1,{\omega }_1)$ in ${ℱ}_{{\nu }_1}$ with every descriptor pair $({\sigma }_2,{\omega }_2)$ in ${ℱ}_{{\nu }_2}$; for every such combination, we assign the two angles at $w$ in the outer face with every possible label in $\{-1,0,1\}$. We test in $O(1)$ time whenever the combination and the assignment result in a descriptor pair $(\sigma ,\omega )$ of a good embedding of $G_{\mu }$, by checking whether the properties of Theorems 1 and 3 are satisfied. In the positive case, we add $(\sigma ,\omega )$ to ${ℱ}_{\mu }$. Thus, the computation of ${ℱ}_{\mu }$ takes time $O(|{ℱ}_{{\nu }_1}|\cdot |{ℱ}_{{\nu }_2}|)$, which is in $O(|V(G_{{\nu }_1})|\cdot |V(G_{{\nu }_2})|)$. This sums up to $O(n^2)$ time over all S-nodes of $T$.

If $\mu$ is a P-node with children ${\nu }_1,\mathrm{\dots },{\nu }_k$, we cannot just combine the descriptor pairs in $ℱ({\nu }_1),\mathrm{\dots },ℱ({\nu }_k)$, as the number of combinations might be super-polynomial. Instead, we consider every descriptor pair that might describe a $uv$-external good embedding of $G_{\mu }$ and test whether it is in ${ℱ}_{\mu }$. This is done as follows. A set ${𝒰}_n$ of descriptor pairs is $n$-universal if: (i) for every $h$-vertex biconnected partitioned directed partial $2$-tree $H$ with $h\le n$, for every two vertices $u_H$ and $v_H$ of $H$, and for every $u_H{v}_H$-external good embedding $({ℰ}_H,{\lambda }_H)$ of $H$, the descriptor pair of $({ℰ}_H,{\lambda }_H)$ is in ${𝒰}_n$, and (ii) for every descriptor pair $(\sigma ,\omega )$ in ${𝒰}_n$, there exists a biconnected partitioned directed partial $2$-tree $H$ that contains two vertices $u_H$ and $v_H$ and admits a $u_H{v}_H$-external good embedding $({ℰ}_H,{\lambda }_H)$ with descriptor pair $(\sigma ,\omega )$. Note that ${ℱ}_{\mu }\subseteq {𝒰}_n$. We can construct an $n$-universal set ${𝒰}_n$ with $|{𝒰}_n|\in O(n)$ in $O(n)$ time.

Consider a $uv$-external good embedding $({ℰ}_{\mu },{\lambda }_{\mu })$ of $G_{\mu }$ with descriptor pair $(\sigma ,\omega )$. Assume, w.l.o.g. up to a change of the indices, that the clockwise order around $u$ in ${ℰ}_{\mu }$ of the pertinent graphs of the children of $\mu$ starting at the outer face is $G_{{\nu }_1},\mathrm{\dots },G_{{\nu }_k}$. The descriptor sequence of $({ℰ}_{\mu },{\lambda }_{\mu })$ is the sequence ${𝒮}_{\mu }=[({\sigma }_1,{\omega }_1),\mathrm{\dots },({\sigma }_k,{\omega }_k)]$ of the descriptor pairs of the $uv$-external good embeddings of $G_{{\nu }_1},\mathrm{\dots },G_{{\nu }_k}$ in $({ℰ}_{\mu },{\lambda }_{\mu })$. The contracted descriptor sequence of $({ℰ}_{\mu },{\lambda }_{\mu })$ is obtained from ${𝒮}_{\mu }$ by identifying equal consecutive descriptor pairs, see Fig. 9. Finally, the generating set $𝒢(\sigma ,\omega )$ for $(\sigma ,\omega )$ is the set of contracted descriptor sequences that a P-node with poles $w$ and $z$ can have in a $wz$-external good embedding with descriptor pair $(\sigma ,\omega )$. We can prove that $𝒢(\sigma ,\omega )$ has size $O(1)$, can be constructed in $O(1)$ time, and that each contracted descriptor sequence in $𝒢(\sigma ,\omega )$ has length $O(1)$.

In order to compute ${ℱ}_{\mu }$, we construct the generating set $𝒢(\sigma ,\omega )$ of $(\sigma ,\omega )$, for each descriptor pair $(\sigma ,\omega )$ in ${𝒰}_n$, in overall $O(n)$ time. For each contracted descriptor sequence $𝒞$ in $𝒢(\sigma ,\omega )$, we test whether $𝒞$ is realizable by $G_{\mu }$, i.e., whether there exists a $uv$-external good embedding of $G_{\mu }$ whose contracted descriptor sequence ${𝒞}^{\prime }$ is a subsequence of $𝒞$ containing the first and last elements of $𝒞$, which ensures that ${𝒞}^{\prime }$ belongs to $𝒢(\sigma ,\omega )$. We decide whether $𝒞$ is realizable by $G_{\mu }$ in $O(k)$ time, by constructing an auxiliary graph with vertex set $(\{{\nu }_1,\mathrm{\dots },{\nu }_k\},\{({\sigma }_1,{\omega }_1),\mathrm{\dots },({\sigma }_{\mathrm{\ell }},{\omega }_{\mathrm{\ell }})\})$ and with an edge between ${\nu }_i$ and $({\sigma }_j,{\omega }_j)$ if $({\sigma }_j,{\omega }_j)$ belongs to ${ℱ}_{{\nu }_i}$, and by then testing whether each vertex in $\{{\nu }_1,\mathrm{\dots },{\nu }_k\}$ can be assigned to a neighbor, so that both $({\sigma }_1,{\omega }_1)$ and $({\sigma }_{\mathrm{\ell }},{\omega }_{\mathrm{\ell }})$ are assigned at least one vertex. We add $(\sigma ,\omega )$ to ${ℱ}_{\mu }$ if some $𝒞$ in $𝒢(\sigma ,\omega )$ is realizable by $G_{\mu }$. Since $|{𝒰}_n|\in O(n)$, $|𝒢(\sigma ,\omega )|\in O(1)$, and the realizability of a contracted descriptor sequence can be decided in $O(k)$ time, the computation of ${ℱ}_{\mu }$ takes $O(nk)$ time, which sums up to $O(n^2)$ time over all P-nodes of $T$.

Finally, if $\mu$ is the root Q-node ${\rho }^{\ast }$, we treat it as a P-node with two children, corresponding to $e^{\ast }$ and $G-e^{\ast }$, and compute ${ℱ}_{{\rho }^{\ast }}$ in $O(n)$ time. Then $G$ has a good embedding with $e^{\ast }$ on the outer face if and only if ${ℱ}_{{\rho }^{\ast }}$ is non-empty. We thus get the following.

We studied upward book embeddings of partitioned digraphs, focusing on the unsolved case of two pages – one of the final open algorithmic book-embedding problems. We closed the complexity gap for the problem by proving its $\mathrm{𝖭𝖯}$-hardness. We provided a characterization of the upward embeddings that admit such layouts and combined this with several algorithmic tools, including flow techniques, SPQ-decompositions, and compact embedding representations, obtaining efficient testing and embedding algorithms for digraphs with a fixed planar embedding and for biconnected partial 2-trees with variable embedding. We aim to (i) remove the linear overhead in our algorithm for biconnected partial 2-trees caused by rerouting the SPQ-tree at each Q-node, and (ii) extend the method to arbitrary simply connected partial 2-trees. The latter is challenging due to nested biconnected components in the block-cut-vertex tree, which must be arranged while keeping cut vertices 4-modal and avoiding impossible faces. Additional research directions include:

• $\mathbf{■}$

  studying the complexity of the problem for partitioned digraphs with few sources;

• $\mathbf{■}$

  determining whether the problem is $\mathrm{𝖭𝖯}$-complete for bounded-treewidth instances; and

• $\mathbf{■}$

  developing FPT algorithms for parameters more restrictive than treewidth.