Extending Upward Planar Graph Drawings

Abstract

In this paper we study the computational complexity of the Upward Planarity Extension problem, which takes as input an upward planar drawing $\varGamma _H$ of a subgraph H of a directed graph G and asks whether $\varGamma _H$ can be extended to an upward planar drawing of G.

We show that the Upward Planarity Extension problem is NP-complete, even if G has a prescribed upward embedding, the vertex set of H coincides with the one of G, and H contains no edge. Conversely, we show that the Upward Planarity Extension problem can be solved in $O(n \log n)$ time if G is an n-vertex upward planar st-graph. This result improves upon a known $O(n^2)$-time algorithm, which however applies to all n-vertex single-source upward planar graphs. We also show how to solve in polynomial time a surprisingly difficult version of the Upward Planarity Extension problem, in which the underlying graph of G is a path or a cycle, G has a prescribed upward embedding, H contains no edges, and no two vertices share the same y-coordinate in $\varGamma _H$.

This research was supported in part by MIUR Project “MODE” under PRIN 20157EFM5C, by MIUR Project “AHeAD” under PRIN 20174LF3T8, by H2020-MSCA-RISE project 734922 – “CONNECT”, and by MIUR-DAAD JMP N$^\circ$ 34120.

1 Introduction

The study of the extensibility of partial representations of graphs has recently become a mainstream in the graph drawing community; see, e.g., [5, 12, 14,15,16, 23,24,25,26,27, 29]. Major contributions in this scenario are the result of Angelini et al. [5], which states that the existence of a planar drawing of a graph G extending a given planar drawing of a subgraph of G can be tested in linear time, and the result of Brückner and Rutter [12], which states that the problem of testing the extensibility of a given partial level planar drawing of a level graph (where each vertex has a prescribed y-coordinate, called level) is NP-complete.

Upward planarity is the natural counterpart of planarity for directed graphs. In an upward planar drawing of a directed graph no two edges cross and an edge directed from a vertex u to a vertex v is represented by a curve monotonically increasing in the y-direction from u to v. The study of upward planar drawings is a most prolific topic in the theory of graph visualization [2,3,4, 6,7,8,9,10,11, 13, 18, 19, 21, 22, 30]. Garg and Tamassia showed that deciding the existence of an upward planar drawing is an NP-complete problem [22]. On the other hand, Bertolazzi et al. [7] showed that testing for the existence of an upward planar drawing belonging to a fixed isotopy class of planar embeddings can be done in polynomial time. Further, Di Battista et al. [19] proved that any upward planar graph is a subgraph of an upward planar st-graph and as such it admits a straight-line upward planar drawing.

In this paper, we consider the extensibility of upward planar drawings of directed graphs. Namely, we introduce and study the complexity of the Upward Planarity Extension (for short, UPE) problem, which is defined as follows. The input is a triple $\langle G, H, \varGamma _H \rangle$, where $\varGamma _H$ is an upward planar drawing of a subgraph H of a directed graph G; we call H and $\varGamma _H$ the partial graph and the partial drawing, respectively. The UPE problem asks whether $\varGamma _H$ can be extended to an upward planar drawing of G; or, equivalently, whether an upward planar drawing of G exists which coincides with $\varGamma _H$ when restricted to the vertices and edges of H. We also study the Upward Planarity Extension with Fixed Upward Embedding (for short, UPE-FUE) problem, which is the UPE problem with the additional requirement that the drawing of G we seek has to respect a given upward embedding, i.e., a left-to-right order of the edges entering and exiting each vertex.

The NP-hardness of the Upward Planarity Testing problem [22] directly implies the NP-hardness of the UPE problem, as the former coincides with the special case of the latter in which the partial graph is the empty graph. In the full version of the paper [17], we prove two stronger NP-hardness results. First, we show that the UPE problem is NP-hard even if the partial graph contains all the vertices and no edges, and no three vertices share the same y-coordinate in the partial drawing. This result is established by means of a simple reduction from the Ordered Level Planarity (OLP) problem, introduced and proved to be NP-complete by Klemz and Rote [28]. The input of the OLP problem is a partial drawing of a level graph containing all the vertices and no edges; the problem asks for the existence of a level planar drawing of the graph extending the partial one. Second, we show that the UPE-FUE problem is NP-hard even for connected instances whose partial graph contains all the vertices and no edges. This result is established by means of a non-trivial reduction from the already mentioned Partial Level Planarity (PLP) problem by Brückner and Rutter [12]. Our result is in contrast with several constrained embedding problems that are NP-hard when the graph has a variable embedding and efficiently solvable in the fixed embedding setting. Some examples are the Upward Planarity Testing problem [7, 22], the Windrose Planarity Testing problem [1], and the notorious Bend Minimization in Planar Orthogonal Drawings problem [22, 31].

We now present an overview of our algorithmic results. First, we identify two main factors that contribute to the complexity of the UPE and UPE-FUE problems: (i) The presence of edges in the partial graph and (ii) the existence of vertices with the same y-coordinate in the partial drawing. These two properties are strictly tied together. Namely, any instance of the UPE or UPE-FUE problems can be efficiently transformed into an equivalent instance $\langle G, H, \varGamma _H \rangle$ of the same problem in which H contains no edges or no two vertices share the same y-coordinate in $\varGamma _H$ (see Sect. 2). Hence, the NP-hardness results for the UPE and UPE-FUE problems discussed above carry over to such instances, even when $V(G)=V(H)$. When the partial graph contains no edges and no two vertices share the same y-coordinate in the partial drawing, then the UPE and UPE-FUE problems appear to be more tractable. Indeed, while we could not establish their computational complexity in general, we could solve them for instances $\langle G, H, \varGamma _H \rangle$ such that the underlying graph of G is a path or a cycle (see Sect. 4). In particular, in order to solve the UPE-FUE problem for paths, we employ a sophisticated dynamic programming approach.

Second, we look at the UPE and UPE-FUE problems for instances $\langle G, H, \varGamma _H \rangle$ such that G is an upward planar st-graph (see Sect. 3), i.e., it has a unique source s and a unique sink t. The upward planarity of an n-vertex st-graph is known to be decidable in O(n) time [19, 21]. We observe that a result of Brückner and Rutter [12] implies the existence of an $O(n^2)$-time algorithm to solve the UPE problem for upward planar st-graphs; their algorithm works more in general for upward planar single-source graphs. We present $O(n \log n)$-time algorithms for the UPE and UPE-FUE problems for upward planar st-graphs. Notably, these results assume neither that the edge set of H is empty, nor that any two vertices have distinct y-coordinates in $\varGamma _H$, nor that $V(G)=V(H)$.

Due to space limitations some theorems and proofs are omitted or sketched and can be found in the full version of the paper [17].

2 Preliminaries

In this section we give some preliminaries and definitions.

Let G be a directed graph. We denote by (u, v) an edge from a vertex u to a vertex v. A path $(u_1,\dots ,u_n)$ in G is directed if it consists of the edges $(u_i,u_{i+1})$, for $i=1,\dots ,n-1$. A vertex v is a successor (predecessor) of a vertex u if G contains a directed path from u to v (from v to u). We denote by $S_G(u)$ (by $P_G(u)$) the set of successors (predecessors) of a vertex u in G.

A drawing of a directed graph G is upward if each edge (u, v) is represented by a curve monotonically increasing in the y-direction from u to v. A graph is upward planar if it admits an upward planar drawing. Consider an upward planar drawing and a vertex v. The list $\mathcal S(v)=[w_1,\dots ,w_k]$ contains the adjacent successors of v in “left-to-right order”. That is, consider a half-line $\ell$ starting at v and directed leftwards; rotate $\ell$ around v in clockwise direction and append a vertex $w_i$ to $\mathcal S(v)$ when $\ell$ overlaps the tangent to the edge $(v,w_i)$ at v. The list $\mathcal P(v)=[z_1,\dots ,z_l]$ of the adjacent predecessors of v is defined similarly. Then two upward planar drawings of a connected directed graph are equivalent if they have the same lists $\mathcal S(v)$ and $\mathcal P(v)$ for each vertex v. An upward embedding is an equivalence class of upward planar drawings. Given an upward planar graph G with a fixed upward embedding, and given a subgraph $G'$ of G, we always implicitly assume that $G'$ inherits the upward embedding from G.

We assume that any instance $\langle G, H, \varGamma _H \rangle$ of the UPE and UPE-FUE problems is such that $\varGamma _H$ is a drawing in which the edges are represented as polygonal lines. Then the size of $\langle G, H, \varGamma _H \rangle$ is $|\langle G, H, \varGamma _H \rangle | = |V(G)| + |E(G)| + s$, where s is the number of segments of the polygonal lines representing the edges in $\varGamma _H$.

Consider an upward planar st-graph G with a fixed upward embedding. In any upward planar drawing of G, every face f is delimited by two directed paths $(u_1,\dots ,u_k)$ and $(v_1,\dots ,v_l)$ connecting the same two vertices $u_1=v_1$ and $u_k=v_l$. Assuming that $\mathcal S(u_1) = [\dots ,u_2,v_2,\dots ]$, we call $(u_1,\dots ,u_k)$ the left boundary of f and $(v_1,\dots ,v_l)$ the right boundary of f. For a vertex $v\ne t$, the leftmost outgoing path $\mathcal L^+_G(v)=(w_1,\dots ,w_m)$ of v is the directed path such that $w_1=v$, $w_m=t$, and $\mathcal S(w_i)=[w_{i+1},\dots ]$, for each $i=1,\dots ,m-1$. The rightmost outgoing path $\mathcal R^+_G(v)$, the leftmost incoming path $\mathcal L^-_G(v)$ and the rightmost incoming path $\mathcal R^-_G(v)$ are defined similarly. The paths $\mathcal L^+_G(s)$ and $\mathcal R^+_G(s)$ are also called leftmost and rightmost path of G, respectively. Note that these paths delimit the outer face of G. Consider a directed path $\mathcal Q$ from s to t. Let $\mathcal Q^*$ be obtained by extending $\mathcal Q$ with a y-monotone curve directed upwards from t to infinity and with a y-monotone curve directed downwards from s to infinity. Then a vertex u is to the left (to the right) of $\mathcal Q$ if it lies in the region to the left (resp. to the right) of $\mathcal Q^*$. In particular, u is to the left of a vertex v if it lies to the left of the directed path composed of $\mathcal L^+_G(v)$ and $\mathcal L^-_G(v)$. Similarly, u is to the right of v if it lies to the right of $\mathcal R^+_G(v)\cup \mathcal R^-_G(v)$. We denote by $L_G(v)$ ($R_G(v)$) the set of vertices that are to the left (resp. right) of a vertex v in G.

2.1 Simplifications

In this section we prove that it is not a loss of generality to restrict our attention to instances $\langle G, H, \varGamma _H \rangle$ of the UPE and UPE-FUE problems in which H contains no edges or no two vertices share the same y-coordinate in $\varGamma _H$.

Lemma 1

Let $\langle G, H, \varGamma _H \rangle$ be an instance of the UPE or UPE-FUE problem and let $n = |\langle G, H, \varGamma _H \rangle |$. There exists an equivalent instance $\langle G', H', \varGamma _{H'} \rangle$ of the UPE or UPE-FUE problem, respectively, such that: (i) $E(H')=\emptyset$, (ii) if $V(H)=V(G)$, then $V(H')=V(G')$, and (iii) if G is an st-graph, then $G'$ is an st-graph. Further, the instance $\langle G', H', \varGamma _{H'} \rangle$ has O(n) size and can be constructed in $O(n \log {n})$ time. The drawing $\varGamma _{H'}$ may contain vertices with the same y-coordinate even if $\varGamma _H$ does not.

Fig. 1.

The drawings $\varGamma _{H}$ (a) and $\varGamma _{H'}$ (b) in the proximity of $\ell ^*_i$. The vertices that are inserted on $\ell ^*_i$ are gray; those inserted on $\ell ^*_{i-1}$ and $\ell ^*_{i+1}$ are not shown.

Proof sketch

The graph $G'$ is obtained from G by replacing the edges of H by directed paths, as described below. Property (iii) is then satisfied. The graph $H'$ is composed of all the vertices of H plus all the internal vertices of the directed paths that are inserted in $G'$ to replace the edges of H. Property (ii) is hence satisfied. Further, $H'$ contains no edge, hence Property (i) is also satisfied. The drawing $\varGamma _{H'}$ coincides with $\varGamma _{H}$ when restricted to the vertices in H. It remains to specify the lengths of the directed paths that are inserted in $G'$ to replace the edges of H and to describe how to place their internal vertices in $\varGamma _{H'}$. This is done in the following.

We compute the increasing order $y^*_1,\dots ,y^*_m$ of the y-coordinates of the vertices of H in $\varGamma _H$. Let $\ell ^*_i$ be the line with equation $y=y^*_i$. Refer to Fig. 1. We look at the left-to-right order $X^*_i$ in which the vertices of H lying on $\ell ^*_i$ and the edges of H crossing $\ell ^*_i$ appear in $\varGamma _{H}$. We place a vertex v in $\varGamma _{H'}$ at the point in which an edge e of H crosses $\ell ^*_i$ if: (i) e is preceded or followed by a vertex of H in $X^*_i$; or (ii) e has an end-vertex whose y-coordinate in $\varGamma _H$ is $y^*_{i-1}$ or $y^*_{i+1}$; in both such cases v is also a vertex that is internal to the directed path that is inserted in $G'$ to replace e. This concludes the construction of $\langle G', H', \varGamma _{H'} \rangle$. The proof is completed by showing that $\langle G, H, \varGamma _H \rangle$ is a positive instance of the UPE or UPE-FUE problem if and only if $\langle G', H', \varGamma _{H'} \rangle$ is.    $\square$

Lemma 2

Let $\langle G, H, \varGamma _H \rangle$ be an instance of the UPE or UPE-FUE problem and let $n = |\langle G, H, \varGamma _H \rangle |$. There exists an equivalent instance $\langle G', H', \varGamma _{H'} \rangle$ of the UPE or UPE-FUE problem, respectively, such that: (i) no two vertices of $H'$ share the same y-coordinate in $\varGamma _{H'}$ and (ii) if $V(H)=V(G)$, then $V(H')=V(G')$. Further, the instance $\langle G', H', \varGamma _{H'} \rangle$ has O(n) size and can be constructed in $O(n \log {n})$ time. The graph $H'$ may contain edges even if H does not.

Fig. 2.

The strip $\mathcal S^*_i$ in the construction of $\langle G', H', \varGamma _{H'} \rangle$.

Proof sketch

By Lemma 1 we can assume that H contains no edges. Let $y^*_1,\dots ,y^*_m$ be the y-coordinates of the vertices of H in $\varGamma _{H}$ in increasing order. Let $\ell ^*_i$ be the line with equation $y=y^*_i$. Let $\mathcal S^*_1,\dots ,\mathcal S^*_m$ be disjoint horizontal strips, where $\ell ^*_i$ is in the interior of $\mathcal S^*_i$, for $i=1,\dots ,m$. Refer to Fig. 2. We define $\langle G', H', \varGamma _{H'} \rangle$ by initializing $G'=G$ and by replacing each vertex $v\in V(H)$ with an edge (u, w), where u gets all the incoming edges of v, while w gets all the outgoing edges of v. The edge (u, w) belongs to $H'$ and is represented in $\varGamma _{H'}$ by a vertical segment with its midpoint at v. Vertical segments corresponding to distinct vertices of H lying on $\ell ^*_i$ have different lengths and lie inside $\mathcal S^*_i$.    $\square$

3 Upward Planar st-Graphs

In this section we study the UPE and UPE-FUE problems for upward planar st-graphs. The following lemma will be useful for our algorithms.

Lemma 3

Let G be an n-vertex upward planar st-graph with a given upward embedding. There exists a data structure to test in O(1) time, for any two vertices u and v of G, whether $v\in S_G(u)$, $v\in P_G(u)$, $v\in L_G(u)$, or $v\in R_G(u)$. Further, such a data structure can be constructed in O(n) time.

Proof sketch

First, we construct the transitive reduction $G^*$ of G, that is, the upward planar st-graph obtained from G by removing all its transitive edges. This can be done in O(n) time. We then exploit the fact that, for each vertex v of G (and of $G^*$), it holds $S_{G^*}(v)=S_{G}(v)$, $P_{G^*}(v)=P_{G}(v)$, $L_{G^*}(v)=L_{G}(v)$, and $R_{G^*}(v)=R_{G}(v)$. We use the O(n)-time algorithm by Di Battista et al. [21] to construct a dominance drawing $\varGamma ^*$ of $G^*$ such that: (i) $x(v)<x(u)$ if and only if $v \in P_G(u) \cup L_G(u)$; and (ii) $y(v)<y(u)$ if and only if $v \in P_G(u) \cup R_G(u)$. Hence, for a query $v\in P_G(u)$, we check whether $x(v)<x(u)$ and $y(v)<y(u)$ in $\varGamma ^*$. The other queries can be similarly answered in O(1) time.    $\square$

We now present one of our main tools to deal with the UPE and UPE-FUE problems for upward planar st-graphs.

Lemma 4

An instance $\langle G, H, \varGamma _H \rangle$ of the UPE-FUE problem such that G is an upward planar st-graph with a given upward embedding and such that H contains no edges is a positive instance if and only if:

• Condition 1: For each vertex v of H, all its successors (predecessors) in G that belong to H have a y-coordinate in $\varGamma _H$ that is larger (smaller) than y(v); and

• Condition 2: For each vertex v of H, all the vertices of H whose y-coordinate is the same as y(v) and whose x-coordinate is larger (smaller) than x(v) in $\varGamma _H$ are to the right (to the left) of v in G.

Proof sketch

Condition 1 is obviously necessary for the existence of an upward drawing of G extending $\varGamma _H$. Suppose that two vertices u, v exist in H such that (i) u is to the left and on the same horizontal line as v in $\varGamma _H$ and (ii) u is to the right of v in G. Then any two minimal directed paths $Q_{uw}$ and $Q_{vw}$ from u and v to a common vertex w determine, in any upward planar drawing of G extending $\varGamma _H$, a list $\mathcal P(w)$ of adjacent predecessors of w that does not respect the upward embedding of G. This proves the necessity of Condition 2.

For the sufficiency, we construct an upward planar drawing $\varGamma _G$ of G that extends $\varGamma _H$. First we draw every vertex of G not in H at an exclusive y-coordinate larger than those of its predecessors and smaller than those of its successors; then the instance still satisfies Conditions 1 and 2. Now we draw the edges of G “one face at a time”. After each step we maintain the invariants that: (i) the subgraph of G currently drawn consists of an upward planar st-graph $G'$ plus a set of isolated vertices; (ii) the current drawing of $G'$ in $\varGamma _G$ is upward planar; and (iii) the rightmost path of $G'$ is represented by a y-monotone curve that has all the isolated vertices to its right. We first draw $\mathcal L^+_G(s)$ so to keep all the vertices not in it to its right; see Fig. 3a. Then, repeatedly, we consider a face f whose left boundary belongs to $G'$ and whose right boundary $(u_1,\dots ,u_l)$ consists of edges not in $G'$; see Fig. 3b. Such a right boundary is a directed path which is drawn upward (this is possible by Condition 1), to the right of the left boundary of f and so close to it that no vertex which is still isolated in the drawing lies to the left of it (this is possible by Condition 2).    $\square$

We can now prove the following algorithmic theorem.

Fig. 3.

(a) Drawing the leftmost path $\mathcal L^+_G(s)$ of G. (b) Drawing the right boundary $(u_1,\dots ,u_l)$ of a face f.

Theorem 1

The UPE-FUE problem can be solved in $O(n \log n)$ time for instances $\langle G, H, \varGamma _H \rangle$ with size $n = |\langle G, H, \varGamma _H \rangle |$ such that G is an upward planar st-graph with a given upward embedding.

Proof sketch

We apply Lemma 1 in $O(n \log n)$ time to modify $\langle G, H, \varGamma _H \rangle$ so that H contains no edges while G remains an upward planar st-graph. Next, we test whether $\langle G, H, \varGamma _H \rangle$ satisfies Conditions 1 and 2 of Lemma 4 in $O(n \log n)$ time.

In order to test Condition 1, we construct an auxiliary graph $\mathcal A$, which we initialize to G. We construct in $O(n\log n)$ time a sequence $\mathcal S$ in which the vertices of H are ordered by increasing y-coordinates and, secondarily, by increasing x-coordinates in $\varGamma _H$. We partition $\mathcal S$ into maximal subsequences $\mathcal S_1,\dots ,\mathcal S_k$ such that all the vertices in $\mathcal S_i$ have the same y-coordinate. For every pair $\mathcal S_i,\mathcal S_{i+1}$ we add to $\mathcal A$ a vertex $v_i$ and directed edges from every vertex in $\mathcal S_i$ to $v_i$ and from $v_i$ to every vertex in $\mathcal S_{i+1}$. Then $\langle G, H, \varGamma _H \rangle$ satisfies Condition 1 if and only if $\mathcal A$ is acyclic. The graph $\mathcal A$ can be constructed in $O(n \log n)$ time; further, it has O(n) vertices and edges, hence it can be tested in O(n) time whether it is acyclic.

In order to test Condition 2, we look at every pair u, v of consecutive vertices in each sequence $\mathcal S_i$ and test whether $u\in L_G(v)$. By Lemma 3, this can be done in O(1) time per query, after an O(n)-time preprocessing.    $\square$

Next, we deal with the UPE problem. Notice that an instance $\langle G, H, \varGamma _H \rangle$ of the UPE problem such that G is an upward planar st-graph can be easily transformed into an equivalent instance of the PLP problem. This is due to the fact that Condition 1 of Lemma 4 does not depend on the upward embedding of G and that we can assume: (i) the edge set of H to be empty, by Lemma 1; and (ii) the partial drawing to contain all the vertices of G, by drawing each vertex in $V(G) \setminus V(H)$ as in the proof of Lemma 4 without violating neither Condition 1 nor Condition 2 of the lemma. Hence, the UPE problem for upward planar st-graphs can be solved in quadratic time, due to the results of Brückner and Rutter about the PLP problem for single-source graphs [12]. However, in the following theorem we show how to reduce the time bound to almost linear.

Theorem 2

The UPE problem can be solved in $O(n \log n)$ time for instances $\langle G, H, \varGamma _H \rangle$ with size $n = |\langle G, H, \varGamma _H \rangle |$ such that G is an upward planar st-graph.

Proof sketch

First, we test in $O(n\log n)$ time whether G satisfies Condition 1 of Lemma 4; this is done as in the proof of Theorem 1. If the test fails, we reject the instance, otherwise we apply Lemma 1 in order to modify $\langle G, H, \varGamma _H \rangle$ so that H contains no edges while G remains an upward planar st-graph.

In order to test whether G admits an upward embedding satisfying Condition 2 of Lemma 4 we proceed as follows. First, we add the edge (s, t) to G, so to ensure the biconnectivity of G. Second, we compute in $O(n \log n)$ time the order $\mathcal {O} = v_1,v_2,\dots ,v_h$ of the vertices in H by increasing y-coordinates and, secondarily, by increasing x-coordinates in $\varGamma _H$. Third, we compute in O(n) time the SPQR-tree $\mathcal T$ of G (see [20] and Fig. 4). The tree $\mathcal T$ represents the recursive arrangement of the triconnected components of G. Roughly speaking, these components might be arranged in a cycle (this corresponds to an S-node in $\mathcal T$), or might share two vertices and be arranged in parallel (this corresponds to a P-node in $\mathcal T$), or might be arranged as in a triconnected graph (this corresponds to an R-node in $\mathcal T$). An auxiliary graph, called skeleton and denoted by $sk(\nu )$, is associated to each node $\nu$ of $\mathcal T$ and represents the corresponding arrangement. Each edge of $sk(\nu )$ corresponds to a subgraph of G, called pertinent graph.

Fig. 4.

(left) A biconnected upward planar st-graph G and (right) the SPQR-tree $\mathcal T$ of G. The skeletons of all the non-leaf nodes of $\mathcal T$ are depicted. The allocation nodes of a vertex v are in the yellow-shaded region.

Any upward embedding of G can be obtained by choosing a left-to-right order for the edges of the skeleton of each P-node of $\mathcal T$ and an upward embedding for the skeleton of each R-node of $\mathcal T$. We outline the approach for performing these choices so to satisfy Condition 2. First, we consider each R-node $\nu$ of $\mathcal T$ and we arbitrarily choose one of the two upward embeddings of $sk(\nu )$; we associate to $\nu$ two boolean variables $preserve(\nu )$ and $flip(\nu )$, that we both initially set to false, respectively indicating whether the arbitrarily chosen embedding of $sk(\nu )$ has to be maintained or changed; finally, we set up in $O(|sk(\nu )|)$ time a data structure that, for a pair (x, y) of vertices or edges of $sk(\nu )$, determines in O(1) time whether $x\in L_{sk(\nu )}(y)$, $x\in R_{sk(\nu )}(y)$, or none of the previous, in the chosen upward embedding of $sk(\nu )$; this can be done by Lemma 3.

We now consider any two vertices $u=v_i$ and $v=v_{i+1}$ with the same y-coordinate in $\varGamma _H$. Note that $x(u)<x(v)$ in $\varGamma _H$. Then $u\in L_G(v)$ in the upward embedding of G we look for. This imposes a constraint on the skeleton $sk(\nu )$ of the lowest common ancestor $\nu$ of the proper allocation nodes of u and v in $\mathcal T$. Specifically: (1) If $\nu$ is an S-node, then we reject the instance. (2) If $\nu$ is a P-node, then we constrain the edge of $sk(\nu )$ whose pertinent graph contains u to precede the edge of $sk(\nu )$ whose pertinent graph contains v. (3) If $\nu$ is an R-node, then let $x_u$ be the representative of u in $sk(\nu )$, that is, if u is a vertex of $sk(\nu )$ then $x_u = u$, otherwise $x_u$ is the edge of $sk(\nu )$ whose pertinent graph contains u. The representative $x_v$ of v in $sk(\nu )$ is defined in the same way. We query in O(1) time the data structure associated to $sk(\nu )$ to test whether $x_u\in L_{sk(\nu )}(x_v)$ (then we set $preserve(\nu ) =\,$true), or $x_u\in R_{sk(\nu )}(x_v)$ (then we set $flip(\nu ) =\,$true), or $x_u\notin L_{sk(\nu )}(x_v)$ and $x_u\notin R_{sk(\nu )}(x_v)$ (then we reject the instance).

Finally, for each P-node $\nu$ of $\mathcal T$, we test whether the precedence constraints imposed on the edges of $sk(\nu )$ induce an acyclic relationship. In case of a negative answer, we reject the instance. For each R-node $\nu$ of $\mathcal T$, we test whether $preserve(\nu ) =\,$false or $flip(\nu ) =\,$false. In case of a negative answer, we reject the instance. Finally, if we did not reject the instance, then we accept it.    $\square$

4 Paths and Cycles

In this section we deal with the UPE and UPE-FUE problems for instances $\langle G,H,\varGamma _H\rangle$ such that the underlying graph of G is a path or a cycle, H contains no edges, and no two vertices share the same y-coordinate in $\varGamma _H$. For the sake of readability, in the following we often just say “path” or “cycle” to address a directed graph whose underlying graph is a path or cycle, respectively.

It turns out that paths and cycles are easy to handle if they do not come with a prescribed upward embedding. Namely, as long as obvious conditions on the y-coordinates of the vertices in the partial drawing are satisfied, an upward planar drawing can be constructed one directed path at a time, so that every new directed path leaves to its left the already drawn directed paths. Hence, we immediately get the following.

Theorem 3

The UPE problem can be solved in O(n) time for instances $\langle G, H, \varGamma _H \rangle$ such that G is an n-vertex directed graph whose underlying graph is a path or a cycle, H contains no edges, and no two vertices share the same y-coordinate in $\varGamma _H$.

Conversely, solving the UPE-FUE problem for paths and cycles, despite the simplicity of their structure, has proved to be challenging.

Theorem 4

The UPE-FUE problem can be solved in $O(n^4)$ time for instances $\langle G, H, \varGamma _H \rangle$ such that G is an n-vertex directed graph whose underlying graph is a path with a given upward embedding, H contains no edges, and no two vertices share the same y-coordinate in $\varGamma _H$.

Proof sketch

Let $G=(u_1,\dots ,u_n)$. We show a decision algorithm for the UPE-FUE problem employing dynamic programming. Namely, we fill a table with entries $t(u_i,u_j,u_m,u_M)$, for all the indices $i,j,m,M\in \{1,\dots ,n\}$ with $i \le m \le j$, $i \le M \le j$, $i\ne j$, and $m\ne M$. Let $G_{i,j}=(u_i,\dots ,u_j)$ and let $\varGamma _{H,i,j}$ be the restriction of $\varGamma _H$ to the vertices of $G_{i,j}$. Then $t(u_i,u_j,u_m,u_M)=$ true if and only if there is an upward planar drawing $\varGamma _{G,i,j}$ of $G_{i,j}$ that extends $\varGamma _{H,i,j}$ in which $u_m$ and $u_M$ are the vertices with the smallest and largest y-coordinate, respectively. If such a drawing $\varGamma _{G,i,j}$ exists, then we say it is valid for $t(u_i,u_j,u_m,u_M)$. The UPE-FUE problem is positive if and only if $t(u_1,u_n,u_m,u_M)=$ true, for some $1 \le m \le n$ and $1 \le M \le n$ with $m\ne M$.

We start by computing the entries $t(u_i,u_j,u_m,u_M)$ such that $G_{i,j}$ is a directed path. Assume that the edge between $u_i$ and $u_{i+1}$ is outgoing $u_i$, the other case is symmetric. Then $t(u_i,u_j,u_m,u_M)=$ true if and only if the following conditions are satisfied: (1) $m=i$; (2) $M=j$; and (3) for any two indices $i'$ and $j'$ such that $i'<j'$ and such that $u_{i'},u_{j'}\in V(H_{i,j})$, we have $y(u_{i'})<y(u_{j'})$ in $\varGamma _{H,i,j}$.

Assume now that $G_{i,j}$ is not a directed path and that the values of all the entries $t(u_i,u_j,u_m,u_M)$ such that $1\le j-i\le x$ have been computed, for some $x\in \{1,2,\dots \}$. After the computation of the entries $t(u_i,u_j,u_m,u_M)$ such that $G_{i,j}$ is a directed path, this is indeed the case with $x=1$. We compute the values of the entries $t(u_i,u_j,u_m,u_M)$ such that $j-i=x+1$. We distinguish three cases, based on how many of the equalities $i=m$, $i=M$, $j=m$, and $j=M$ are satisfied, that is, based on how many vertices among $u_m$ and $u_M$ are end-vertices of $G_{i,j}$. Refer to Figs. 5a to c.

Fig. 5.

(a)–(c) Three cases for the computation of the value of $t(u_i,u_j,u_m,u_M)$. (d) Illustration for the necessity of Condition (6).

In each case we characterize whether $t(u_i,u_j,u_m,u_M)=$ true based on the values of already computed entries of the table and on the possibility of $u_m$ and $u_M$ to be the lowest and highest vertex in an upward planar drawing of $G_{i,j}$ extending $\varGamma _{H,i,j}$, respectively. In this proof sketch, we present such a characterization only for the (most difficult) case in which $u_m$ and $u_M$ are both end-vertices of $G_{i,j}$. We have that $t(u_i,u_j,u_i,u_j)=$ true if and only if there exist indices $M'\in \{i+1,\dots ,j-2\}$ and $m'\in \{M'+1,\dots ,j-1\}$ such that:

(1) :

$t(u_i,u_{M'},u_i,u_{M'})=$ true;

(2) :

$t(u_{M'},u_{m'},u_{m'},u_{M'})=$ true;

(3) :

$t(u_{m'},u_j,u_{m'},u_j)=$ true;

(4) :

either $u_i$ does not belong to H or $u_i$ has the smallest y-coordinate among the vertices of $G_{i,j}$ in $\varGamma _H$;

(5) :

either $u_j$ does not belong to H or $u_j$ has the largest y-coordinate among the vertices of $G_{i,j}$ in $\varGamma _H$; and

(6) :

either $\mathcal P(u_{M'})=[u_{M'-1},u_{M'+1}]$ and $\mathcal S(u_{m'})=[u_{m'-1},u_{m'+1}]$, or $\mathcal P(u_{M'})=[u_{M'+1},u_{M'-1}]$ and $\mathcal S(u_{m'})=[u_{m'+1},u_{m'-1}]$.

For the necessity, consider a valid drawing $\varGamma _{G,i,j}$ for $t(u_i,u_j,u_i,u_j)$. Then define $u_{M'}$ as the internal sink of $G_{i,j}$ with the largest y-coordinate in $\varGamma _{G,i,j}$ and $u_{m'}$ as the internal source of $G_{M',j}$ with the smallest y-coordinate in $\varGamma _{G,i,j}$. Restricting $\varGamma _{G,i,j}$ to the vertices and edges of $G_{i,M'}$, $G_{M',m'}$, and $G_{m',j}$ yields valid drawings for $t(u_i,u_{M'},u_i,u_{M'})$, $t(u_{M'},u_{m'},u_{m'},u_{M'})$, and $t(u_{m'},u_j,u_{m'},u_j)$, respectively, which proves the necessity of Conditions (1)–(3). Conditions (4)–(5) hold true since $u_i$ and $u_j$ are the vertices with the smallest and largest y-coordinate in $\varGamma _{G,i,j}$, respectively. Finally, the necessity of Condition (6) is proved by observing that if, say, $\mathcal P(u_{M'})=[u_{M'-1},u_{M'+1}]$ and $\mathcal S(u_{m'})=[u_{m'+1},u_{m'-1}]$, then $\varGamma _{G,i,j}$ contains a crossing, as in Fig. 5d.

For the sufficiency, we start from valid drawings $\varGamma _{G,i,M'}$, $\varGamma _{G,M',m'}$, and $\varGamma _{G,m',j}$ for $t(u_i,u_{M'},u_i,u_{M'})$, $t(u_{M'},u_{m'},u_{m'},u_{M'})$, and $t(u_{m'},u_j,u_{m'},u_j)$. We modify $\varGamma _{G,i,M'}$, $\varGamma _{G,M',m'}$, and $\varGamma _{G,m',j}$ so that $u_{M'}$ is at the same point in $\varGamma _{G,i,M'}$ and $\varGamma _{G,M',m'}$, $u_{m'}$ is at the same point in $\varGamma _{G,M',m'}$ and $\varGamma _{G,m',j}$, and $u_i$ ($u_j$) has the smallest (resp. largest) y-coordinate among all the vertices in $\varGamma _{G,i,M'}$, $\varGamma _{G,M',m'}$, and $\varGamma _{G,m',j}$. Satisfying these properties might require modifying the placement of $u_{i}$, $u_{M'}$, $u_{m'}$, and $u_{j}$, and scaling parts of $\varGamma _{G,i,M'}$, $\varGamma _{G,M',m'}$, and $\varGamma _{G,m',j}$. Gluing together these drawings results in an upward drawing $\varGamma _{G,i,j}$ of $G_{i,j}$ that extends $\varGamma _{H,i,j}$ and in which $u_i$ and $u_j$ are the vertices with the smallest and largest y-coordinate, respectively. However, $\varGamma _{G,i,j}$ might contain crossings and the left-to-right order of the edges incoming at $u_{M'}$ (outgoing from $u_{m'}$) in $\varGamma _{G,i,j}$ might not correspond to $\mathcal P(u_{M'})$ (resp. to $\mathcal S(u_{m'})$). We overcome these issues by redrawing the curves representing the edges of $G_{i,M'}$, $G_{M',m'}$, and $G_{m',j}$ in internally-disjoint regions of the plane, without changing the position of any vertex.

The quartic running time comes from the number of entries of the dynamic programming table, which is in fact $\varTheta (n^4)$.    $\square$

By exploiting arguments analogous to those in the proof of Theorem 4 we can extend our quartic-time algorithm to cycles.

Theorem 5

The UPE-FUE problem can be solved in $O(n^4)$ time for instances $\langle G, H, \varGamma _H \rangle$ such that G is an n-vertex cycle with given upward embedding, H contains no edges, and no two vertices share the same y-coordinate in $\varGamma _H$.

Proof

Suppose that an upward planar drawing $\varGamma _G$ of $G=(u_1,\dots ,u_n)$ extending $\varGamma _H$ exists. Since no two vertices share the same y-coordinate in $\varGamma _H$, we can assume w.l.o.g. that no two vertices share the same y-coordinate in $\varGamma _G$ either. Our strategy is to test, for every possible pair of vertices $(u_m,u_M)$ with $m,M\in \{1,\dots ,n\}$ and with $m\ne M$, whether there is an upward planar drawing $\varGamma _G$ of G extending $\varGamma _H$ in which the vertices with the smallest and largest y-coordinate are $u_m$ and $u_M$, respectively. For any pair $(u_m,u_M)$, the cycle G consists of two paths connecting $u_m$ and $u_M$, call them $G_{m,M}=(u_m,u_{m+1},\dots ,u_M)$ and $G_{M,m}=(u_M,u_{M+1},\dots ,u_m)$, where indices are modulo n. Let $\varGamma _{H,m,M}$ and $\varGamma _{H,M,m}$ be the restrictions of $\varGamma _H$ to the vertices that belong to $G_{m,M}$ and $G_{M,m}$, respectively. Then, G has an upward planar drawing extending $\varGamma _H$ in which the vertices with the smallest and largest y-coordinate are $u_m$ and $u_M$, respectively, if and only if: (1) $G_{m,M}$ has an upward planar drawing extending $\varGamma _{H,m,M}$ in which the vertices with the smallest and largest y-coordinate are $u_m$ and $u_M$, respectively; (2) $G_{M,m}$ has an upward planar drawing extending $\varGamma _{H,M,m}$ in which the vertices with the smallest and largest y-coordinate are $u_m$ and $u_M$, respectively; and (3) either $\mathcal P(u_{M})=[u_{M-1},u_{M+1}]$ and $\mathcal S(u_{m})=[u_{m+1},u_{m-1}]$, or $\mathcal P(u_{M})=[u_{M+1},u_{M-1}]$ and $\mathcal S(u_{m})=[u_{m-1},u_{m+1}]$.

From a computational point of view, we act as follows. First we compute, for every possible pair of vertices $(u_m,u_M)$ with $m,M\in \{1,\dots ,n\}$ and with $m\ne M$, whether there are upward planar drawings of $G_{m,M}$ and $G_{M,m}$ extending $\varGamma _{H,m,M}$ and $\varGamma _{H,M,m}$, respectively, in which the vertex with the smallest y-coordinate is $u_m$ and the vertex with the largest y-coordinate is $u_M$. This can be done by considering the 2n-vertex path $(u_1,u_2,\dots ,u_n,u_{n+1}=u_1,u_{n+2}=u_2,\dots ,u_{2n}=u_n)$ and by setting up a dynamic programming table with entries $t(u_i,u_j,u_{m'},u_{M'})$, for all the indices $i,j,m',M'\in \{1,\dots ,2n\}$ such that $i \le m' \le j$ and $i \le M' \le j$, with $i\ne j$, $m'\ne M'$, and $j-i\le n$. The values of the entries of this table can be computed in total $O(n^4)$ time as in the proof of Theorem 4.

Then, for each of the $O(n^2)$ pairs of vertices $(u_m,u_M)$ with $m,M\in \{1,\dots ,n\}$ and with $m\ne M$, we query the table constructed in the step above to check whether G has an upward planar drawing extending $\varGamma _H$ in which the vertices with the smallest and largest y-coordinate are $u_m$ and $u_M$, respectively. Concerning Conditions (1) and (2), we check in O(1) time whether $t(u_m,u_M,u_m,u_M)=$ true and $t(u_M,u_{n+m},u_{n+m},u_M)=$ true (if $m<M$) or whether $t(u_M,u_m,u_m,u_M)=$ true and $t(u_m,u_{n+M},u_m,u_{n+M})=$ true (if $m>M$). Condition (3) can also be trivially checked in O(1) time.    $\square$

5 Conclusions and Open Problems

In this paper we introduced and studied the Upward Planarity Extension (UPE) problem, which takes as input an upward planar drawing $\varGamma _H$ of a subgraph H of a directed graph G and asks whether an upward planar drawing of G exists which coincides with $\varGamma _H$ when restricted to the vertices and edges of H.

We proved that the UPE problem is NP-complete, even if G has a prescribed upward embedding and H contains all the vertices and no edges. Conversely, the problem can be solved efficiently for upward planar st-graphs.

Several questions are left open by our research. We cite our favorite two. First, is it possible to solve the UPE-FUE problem in polynomial time for instances $\langle G,H,\varGamma _H\rangle$ such that H contains no edges and no two vertices have the same y-coordinate in $\varGamma _H$? We proved that if any of the two conditions is dropped, then the UPE-FUE problem is NP-hard, however we can positively answer the above question only if G is a directed path or cycle. Second, are the UPE and UPE-FUE problems polynomial-time solvable for directed paths and cycles? Even when H contains no edges and no two vertices have the same y-coordinate in $\varGamma _H$, answering the above question in the affirmative was not a trivial task.