Upward planar drawings with two slopes

Consider an upward planar embedding of $G$ and suppose $e=(u,v)$ is a bad edge with respect to the outer face $f_{0}$; see Figure 7 (a). Let $e^{\prime}$ be the second incoming edge of $v$. Then $v$ is a local sink of $f_{0}$ such that if $e$ and $e^{\prime}$ would be drawn with slopes $\nearrow$ and $\nwarrow$ accordingly, then $f_{0}$ would have a small angle at $v$. However, this implies that there are two local sources ($w_{1}$ and $w_{2}$ in Figure 7 (a)) of $f_{0}$ that are also sources of $G$. This is a contradiction to $G$ being a single-source digraph.

Let $G$ be an upward plane single-source digraph and let $f$ be a face of $G$. Note that a bad edge $e$ with respect to $f$ is incident to a local sink $v$ of a face $f$ where $v$ lies between its two incoming edges in a counterclockwise traverse of the boundary of $f$. In other words, in an upward planar drawing of $G$, $f$ would have a (small) angle of less than 180^∘ at $v$. If there are three or more bad edges with respect to $f$, then $f$ contains at least two such local sinks (like $v_{1}$ and $v_{2}$ in Figure 7 (b)). There is then at least one local source $u$ for $f$ that would span a large angle in $f$, i.e., more than 180^∘. However, $u$ is also a source of $G$ and since it is not the source for the outer face, it is not the only source of $G$. This is a contradiction to $G$ being a single-source digraph. Figure 7 (c) gives an example of a face with two bad edges.

Let $e_{1}=e=(u,v)$, let $e_{u}$ be the second outgoing edge of $u$, and let $e_{v}$ be the second incoming edge of $v$. Note that $e_{v}$ and $e_{u}$ are also on the boundary of $f$ and that by Lemma 4.3, $f$ is not the outer face. We claim that $e$ cannot be a bridge. Assume otherwise and let $G_{u}$ and $G_{v}$ be the components of $G\setminus\{e\}$ that contain $u$ and $v$, respectively. Note that both $G_{u}$ and $G_{v}$ have a source each and $v$ cannot be the source of $G_{v}$. This implies that $G$ has two sources, which is a contradiction to $G$ being a single-source digraph. Let $f^{\prime}$ be the second face with $e$ on its boundary, which exists since $e$ is not a bridge. Without loss of generality, assume that $f^{\prime}$ is to the left and $f$ to the right of $e$.

For $G$ to admit an upward planar embedding where $e$ is not a bad edge, it must be possible to change, without loss of generality, the order of $e_{u}$ and $e$ at $u$, that is, $e_{u}$ and $e$ need to become the left and right outgoing edges of $u$, respectively. If $e_{u}$ is a bridge (and thus has $f$ as left and right face), then we can swap $e$ and $e_{u}$ at $u$ and flip the component that does not contain $u$ of $G\setminus\{e_{u}\}$; see Figure 8 (a). We can find out whether $e_{u}$ is a bridge with a single traverse of $f$. Furthermore, clearly, this flip does not introduce a new bad edge.

Otherwise, if $e_{u}$ is not a bridge, observe that we need to flip a subgraph $G^{\prime}$ of $G$ that contains $e_{u}$ and that is enclosed by $f^{\prime}$ and $f$; see Figure 8 (b). For such $G^{\prime}$ to exist, there must be a vertex $w$ that forms a split pair with $u$, and that has $f$ to the right and $f^{\prime}$ to the left. It can be seen as a split pair $\{u,w^{\prime}\}$ without this property does not yield a flippable digraph $G^{\prime}$ (as in Figure 9 (a)) and if no such a split pair exists at all, then the triconnectedness implies that $e_{v}$, $e$, and $e_{u}$ always lie on the boundary of the same face (as in Figure 9 (b)). Assuming now that such $w$ exists, we can define $G^{\prime}$ as the digraph consisting of all split components of $G$ with respect to $\{w,u\}$ that do not contain $v$. To repair $e$, we flip $G^{\prime}$ as shown in Figure 8 (b), that is, we reverse the order of incoming and outgoing edges for each vertex in $G^{\prime}$ except for $w$, where we only reverse the order of the outgoing edges. Note that the flip cannot introduce a new bad edge since $w$ is not a local sink or local source of $f$ or $f^{\prime}$. Furthermore, note that such $w$ precedes $u$, since otherwise both $G^{\prime}$ and $G\setminus G^{\prime}$ would contain a source (that is not $w$) each, which contradicts $G$ being a single-source digraph; see Figure 9 (c). Hence, we may find $w$ with a traverse of $f$.

Lastly, we show that changing the order of $e$ and $e_{v}$ at $v$ is possible only when the case above applies where the order of $e$ and $e_{u}$ at $u$ can be changed. To begin with, note that $e_{v}$ cannot be a bridge, since $G$ is a single-source digraph. Hence, we would need to flip again a digraph $G^{\prime}$ that contains $e_{v}$ and that is enclosed by $f$ and $f^{\prime}$. Such $G^{\prime}$ would imply a split pair $\{w^{\prime},v\}$, where, however, $w^{\prime}$ would also serve as split pair $\{w^{\prime},u\}$ as in Figure 8 (b).

Since we can check whether $e_{u}$ is a bridge or find a suitable $w$ with a single traverse of $f$, the claim on the running time holds.

As noted above, we may assume that $G$ does not contain a leaf. A linear-time algorithm to compute an upward planar 2-slope drawing of $G$ then works as follows. First, compute an upward planar embedding of $G$ with the algorithm of Bertolazzi et al. [6] in $\mathcal{O}(n)$ time. Second, to identify all bad edges in $\mathcal{O}(n)$ time it suffices to traverse the boundary of each face since every bad edge is bad with respect to exactly one face. Third, for each bad edge $e=(u,v)$ with respect to a face $f$, check whether it can be repaired with Lemma 4.7. To keep track of where we have to flip the edge order at vertices, we use two types of markers. A green marker at a vertex $x$ indicates that the outgoing edges of $x$ should be swapped and that both incoming and outgoing edges of the vertices “above” $x$ should be reversed. We thus mark $u$ green if $e$ can be repaired because the respective edge $e_{u}$ is a bridge and we mark $w$ green if $e$ can be repaired because of a respective split pair $\{w,u\}$. Furthermore, we mark $e$ red to tells us to stop reversing edge orders. Both the check and the marking can be done in $\mathcal{O}(\lvert f\rvert)$ time. Since by Lemma 4.5 any face contains at most two bad edges, this step takes overall also only $\mathcal{O}(n)$ time.

Suppose every bad edge can be fixed. Then run a BFS on $G$ that starts at the source. During the traversal, remember along each path the number of green marked vertices minus the number of encountered red edges. Then for each vertex $v$, use the parity of this number to decide whether its edge orders have to be reversed; if odd, then reverse, and if even, then do not. Vertices marked green need to be handled appropriately. This takes again only linear time and as a result we get an upward planar embedding of $G$ that admits a 2-slope representation $U_{G}$. Finally, apply the algorithm from Theorem 3.3 on $U_{G}$ to compute an upward planar 2-slope drawing of $G$.

To compute a feasible tuple $\tau$ of ${\mathcal{F}}_{\mu}$ we check for all pairs $\tau_{1}\in{\mathcal{F}}_{\mu_{1}}$ and $\tau_{2}\in{\mathcal{F}}_{\mu_{2}}$ whether they can be combined. More precisely, let $u$ be the first and $v$ the second pole of $\mu$; refer to Figure 13. Let $u_{i}$ be the first and $v_{i}$ be the second pole of $\mu_{i}$, $i\in\{1,2\}$. Without loss of generality, assume that $u=u_{1}$, $v_{1}=u_{2}$, and $v_{2}=v$. For each pair of feasible tuples $\tau_{1}=\langle U_{G_{\mu_{1}}},\sigma_{1},t_{u_{1}},t_{v_{1}}\rangle\in{\mathcal{F}}_{\mu_{1}}$ and $\tau_{2}=\langle U_{G_{\mu_{2}}},\sigma_{2},t_{u_{2}},t_{v_{2}}\rangle\in{\mathcal{F}}_{\mu_{2}}$ check whether $t_{v_{1}}$ and $t_{u_{2}}$ are compatible. In other words, check whether $G_{\mu_{1}}$ and $G_{\mu_{2}}$ can be plugged together at $v_{1}=u_{2}$ under the slope assignments of $U_{G_{\mu_{1}}}$ and $U_{G_{\mu_{2}}}$ and with the reference edge on the outer face.

If the pole categories are compatible, the feasible tuple $\tau=\langle U_{G_{\mu}},\sigma,t_{u},t_{v}\rangle$ is given by $t_{u}=t_{u_{1}}$, $t_{v}=t_{v_{2}}$, $U_{G_{\mu}}$ as the series composition of $U_{G_{\mu_{1}}}$ and $U_{G_{\mu_{2}}}$ at the common vertex $u_{2}=v_{1}$, and where $\sigma$ can be computed as follows. For $i\in\{1,2\}$, let $e_{l}^{i}$ and $e_{r}^{i}$ be the edges of $U_{G_{\mu_{i}}}$ that are incident to $u_{2}=v_{1}$ and lie on the clockwise and counterclockwise path from $u$ to $v$ along the outer face, respectively; see Figure 13 (b). Note that $e_{l}^{i}$ may coincide with $e_{r}^{i}$. For $j\in\{l,r\}$, let $\alpha_{j}$ be $-1$, $1$, or $0$ depending on whether $e_{j}^{1}$ and $e_{j}^{2}$ make a left, right, or no turn, respectively. The upward $2$-slope spirality of $U_{G_{\mu}}$ is $\sigma=\sigma_{1}+\sigma_{2}+\frac{\alpha_{l}+\alpha_{r}}{2}$ (compare to Lemma 6.4 by Didimo et al. [20]). Store $\tau$ in ${\mathcal{F}}_{\mu}$ if ${\mathcal{F}}_{\mu}$ contains no feasible tuple with spirality equivalent to $\tau$. Since ${\mathcal{F}}_{\mu_{1}}$ and ${\mathcal{F}}_{\mu_{2}}$ have $\mathcal{O}(n)$ tuples, ${\mathcal{F}}_{\mu}$ can be computed in $\mathcal{O}(n^{2})$ time.

Let $u$ be the first and $v$ the second pole of $\mu$ (and its children). Since $u$ and $v$ have at most degree four in $G$, $\mu$ has at most four children (but at least two). We first consider the case where $\mu$ has three children. The cases where $\mu$ has two or four children are discussed at the end of this proof.

For $i\in\{1,2,3\}$, let $G_{i}$ be the pertinent digraph of $\mu_{i}$. Note that $u$ and $v$ have degree one in $G_{i}$. We can thus define $e_{i}$ and $e_{i}^{\prime}$ as the edges of $G_{i}$ incident to $u$ and $v$, respectively. (If $\mu_{i}$ is a Q-node, then $e_{i}=e_{i}^{\prime}$.) Let $e_{u}$ and $e_{v}$ be the edges of $G$ incident to $u$ and $v$, respectively, that lie outside of $G_{\mu}$. (Note that $e_{u}=e_{v}$ is only possible in the final composition, where $e_{u}$ is then also the reference edge.) We want to construct a $2$-slope representation of $G_{\mu}$ such that the order of $e_{1},e_{2},e_{3},e_{u}$ at $u$ is the reverse order of $e_{1}^{\prime},e_{2}^{\prime},e_{3}^{\prime},e_{v}$ at $v$; see Figure 14 (a). Furthermore, the half edges representing $e_{u}$ and $e_{v}$ have to be on the outer face.

Suppose we pick a feasible tuple $\tau_{1}=\langle U_{G_{1}},\sigma_{1},t_{u_{1}},t_{v_{1}}\rangle\in{\mathcal{F}}_{\mu_{1}}$. Then $t_{u_{1}}$ and $t_{u_{2}}$ restrict the choices of pole categories of compatible upward $2$-slope representations of $G_{2}$ and $G_{3}$. Likewise, $\sigma_{1}$ restricts these choices further; see Figure 14 (b) and (c). More precisely, we observe that the upward $2$-slope spirality $\sigma_{2}$ and $\sigma_{3}$ of compatible $U_{G_{2}}$ and $U_{G_{3}}$ differ from $\sigma_{1}$ by at least two and at most six (compare to Lemma 6.6 by Didimo et al. [20]). Therefore, when trying all possible permutations of $G_{1}$, $G_{2}$, and $G_{3}$, we only have to consider $\mathcal{O}(1)$ feasible tuples in ${\mathcal{F}}_{\mu_{2}}$ and ${\mathcal{F}}_{\mu_{3}}$ instead of iterating over complete sets. Storing the feasible tuples in a hash table based on the spirality and pole categories we can find compatible $\tau_{2}$ and $\tau_{3}$ in constant time. Similar to the series-composition, we can compute the upward $2$-slope spirality of the resulting upward $2$-slope representation $U_{G_{\mu}}$ based on its categories and $\sigma_{i}$, $i\in\{1,2,3\}$. More precisely, for this purpose we not only stored each $\sigma_{i}$ but also the respective values $\operatorname{\mathrm{n}}(P_{l})$ and $\operatorname{\mathrm{n}}(P_{r})$ to compute them. Therefore, we can take the appropriate values from the two 2-slope representations of $U_{G_{i}}$, $i\in\{1,2,3\}$, that are on the outer face. Overall, we get that by iterating once over ${\mathcal{F}}_{\mu_{1}}$ we can construct all feasible tuples of ${\mathcal{F}}_{\mu}$ in $\mathcal{O}(n)$ time.

The case where $\mu$ has four children is only possible in the final composition with the reference edge $e$. Here the algorithms works along the same line with the difference that the half edges $e_{u}$ and $e_{v}$ are replaced with $e$. The case where $\mu$ has two children, works analogously with the difference that for some feasible tuples of $U_{G_{1}}$ there can now be more compatible upward spirality values for $U_{G_{2}}$ than above. However, these are still $\mathcal{O}(1)$ many and the running time is thus not affected.

Let $e$ be an edge of $G$. Compute the (canonical) SPQR-tree $T$ with respect to $e$ of $G$, which can be done in $\mathcal{O}(n)$ time [25, 20]. In a post-order traversal of $T$, the algorithm computes the feasible set for every node of $T$. If the algorithm arrives at a node with an empty feasible set, its starts with another reference of $G$. Otherwise, the algorithm stops when it has constructed a feasible tuple for $G$. We can then use Theorem 3.3 to construct an upward planar 2-slope drawing. For one reference edge, this takes at most $\mathcal{O}(n^{2})$ time per node by Lemmas 4.12 and 4.14. and since the size of $T$ is linear in $n$, at most $\mathcal{O}(n^{3})$ time in total. The total running time is thus in $\mathcal{O}(n^{4})$.

Note that since $\mathit{skel}(\mu)$ is triconnected, it has a unique planar embedding (up to mirroring), which we can compute in $\mathcal{O}(n)$ time. Note that, by Theorem 3.3, if $\mathit{skel}(\mu)$ contains a bad edge with respect to three non-virtual edges, then ${\mathcal{F}}_{\mu}$ is empty. Moreover, then $G$ admits no upward planar 2-slope drawing and the main algorithm can stop. So suppose no such bad edge exists.

Construct a 2-slope representation of $G_{\mu}$ by substituting virtual edges with the respective 2-slope representations. More precisely, for all $i\in\{1,\ldots,k\}$, substitute $e_{i}$ with the $2$-slope representation $U_{G_{\mu_{i}}}$ of a feasible tuple in ${\mathcal{F}}_{\mu_{i}}$. Let $U_{G_{\mu}}^{\prime}$ denote the partial upward $2$-slope representation of $G_{\mu}$ during this process, that is, $U_{G_{\mu}}^{\prime}$ consists of an embedding of $G_{\mu}$ and the 2-slope assignment for all edges of the $U_{G_{\mu_{i}}}$, for $i\in\{1,\ldots,k\}$. At each pole of a child $\mu_{i}$ in $U_{G_{\mu}}^{\prime}$ check whether the $2$-slope representations of the substituted parts are conflicting. If this check fails, backtrack and try another feasible tuple. Suppose that it is successful for all poles of all $\mu_{i}$. Then test the upward planarity of $U_{G_{\mu}}^{\prime}$ with the flow-based upward planarity algorithm for triconnected digraphs by Bertolazzi et al. [5] where the assignment of switches to faces is given for the substituted parts (derived from $U_{G_{\mu}}^{\prime}$). This flow-based algorithm runs in $\mathcal{O}(n^{2})$ time.

If $U_{G_{\mu}}^{\prime}$ is upward planar, check whether $U_{G_{\mu}}^{\prime}$ contains any bad edge and, if not, extend $U_{G_{\mu}}^{\prime}$ to a $2$-slope representation $U_{G_{\mu}}$ of $G_{\mu}$ (compare to Lemma 8.2 by Didimo et al. [20]). Suppose there is an edge $(x,y)$ on the outer face of $U_{G_{\mu}}$ that is the sole outgoing edge of $x$ and the sole incoming edge of $y$. Note that the choice of slope for $(x,y)$ does not influence the spirality of $U_{G_{\mu}}$, since the angles formed at $x$ and $y$ always add up to the same value; see Figure 15. Lastly, compute the upward $2$-slope spirality of $U_{G_{\mu}}$ in $\mathcal{O}(n)$ time to obtain a feasible tuple for ${\mathcal{F}}_{\mu}$. By backtracking and trying the remaining feasible tuples of the $\mu_{i}$, we complete the computation of ${\mathcal{F}}_{\mu}$.

Note that $d$ is an upper bound on the upward $2$-slope spirality of a split component and thus each $\mu_{i}$ has $\mathcal{O}(d)$ feasible tuples. Therefore the algorithm tries at most $\mathcal{O}(d^{k})$ combinations of feasible tuples of the $k$ children of $\mu$. Hence the feasible set of an R-node $\mu$ can be computed in $\mathcal{O}(d^{k}n^{2})$ time, where the factor $\mathcal{O}(n^{2})$ comes from the flow based upward planarity test.