Upward Planar Morphs

Abstract

We prove that, given two topologically-equivalent upward planar straight-line drawings of an n-vertex directed graph G, there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of O(1) morphing steps if G is a reduced planar st-graph, O(n) morphing steps if G is a planar st-graph, O(n) morphing steps if G is a reduced upward planar graph, and $O(n^2)$ morphing steps if G is a general upward planar graph. Further, we show that $\varOmega (n)$ morphing steps might be necessary for an upward planar morph between two topologically-equivalent upward planar straight-line drawings of an n-vertex path.

1 Introduction

One of the definitions of the word morph that can be found in English dictionaries is “to gradually change into a different image”. The Graph Drawing community defines the morph of graph drawings similarly. Namely, given two drawings $\varGamma _0$ and $\varGamma _1$ of a graph G, a morph between $\varGamma _0$ and $\varGamma _1$ is a continuously changing family of drawings of G indexed by time $t \in [ 0,1 ]$, such that the drawing at time $t=0$ is $\varGamma _0$ and the drawing at time $t=1$ is $\varGamma _1$. Further, the way the Graph Drawing community adopted the word morph is consistent with its Ancient Greek root $\mu \omega \rho \phi \acute{\eta }$, which means “shape” in a broad sense. Namely, if both $\varGamma _0$ and $\varGamma _1$ have a certain geometric property, it is desirable that all the drawings of the morph also have the same property. In particular, we talk about a planar, a straight-line, an orthogonal, or a convex morph if all the intermediate drawings of the morph are planar (edges do not cross), straight-line (edges are straight-line segments), orthogonal (edges are polygonal lines composed of horizontal and vertical segments), or convex (the drawings are planar and straight-line, and the faces are delimited by convex polygons), respectively.

The state of the art on planar morphs covers more than 100 years, starting from the 1914/1917 works of Tietze [35] and Smith [31]. The seminal papers of Cairns [14] and Thomassen [34] proved the existence of a planar straight-line morph between any two topologically-equivalent planar straight-line drawings of a graph. In the last 10 years, the attention of the research community focused on algorithms for constructing planar morphs with few morphing steps (see, e.g., [1,2,3,4,5,6,7,8, 12, 13, 28, 36]). Each morphing step, sometimes simply called step, is a linear morph, in which the vertices move along straight-line (possibly distinct) trajectories at uniform speed. A unidirectional morph is a linear morph in which the vertex trajectories are all parallel. It is known [2, 4] that a planar straight-line morph with a linear number of unidirectional morphing steps exists between any two topologically-equivalent planar straight-line drawings of the same graph, and that this bound is the best possible.

Upward planarity is usually regarded as the natural extension of planarity to directed graphs; see, e.g., [10, 11, 16, 18, 19, 23]. A drawing of a directed graph is upward planar if it is planar and the edges are represented by curves monotonically increasing in the vertical direction. Despite the fact that upward planarity is a widely-investigated research topic, no algorithm has been devised, up to now, to morph upward planar drawings of directed graphs. This paper deals with the following question: Given two topologically-equivalent¹ upward planar drawings $\varGamma _0$ and $\varGamma _1$ of an upward planar directed graph G, does an upward planar straight-line morph between $\varGamma _0$ and $\varGamma _1$ always exist? In this paper we give a positive answer to this question.

Problems related to upward planar graphs are usually more difficult than the corresponding problems for undirected graphs. For example, planarity can be tested in linear time [25] while testing upward planarity is NP-complete [23]; all planar graphs admit planar straight-line grid drawings with polynomial area [30] while there are upward planar graphs that require exponential area in any upward planar straight-line grid drawing [20]. On the other hand, we show that, from the morphing point of view, the difference between planarity and upward planarity is less sharp; indeed, in some cases, upward planar straight-line drawings can be morphed even more efficiently than planar straight-line drawings. This is due to the fact that two topologically-equivalent upward planar drawings of the same directed graph are, in general, “more similar” to each other than two topologically-equivalent planar drawings of the same graph, as the latter do not need to comply with the edge orientations.

More in detail, our results are as follows. Let $\varGamma _0$ and $\varGamma _1$ be topologically-equivalent upward planar drawings of an n-vertex upward plane graph G. We show algorithms to construct upward planar straight-line morphs between $\varGamma _0$ and $\varGamma _1$ with the following number of morphing steps:

• 1. O(1) steps if G is a reduced plane st-graph;

• 2. O(n) steps if G is a plane st-graph;

• 3. O(n) steps if G is a reduced upward plane graph;

• 4. $O(n\cdot f(n))$ steps if G is a general upward plane graph, assuming that an O(f(n))-step algorithm exists to construct an upward planar morph between any two upward planar drawings of any n-vertex plane st-graph. This, together with Result (2), yields an $O(n^2)$-step upward planar morph for general upward plane graphs.

Further, we show that there exist two topologically-equivalent upward planar drawings of an n-vertex upward plane path such that any upward planar morph between them consists of $\varOmega (n)$ morphing steps.

In order to prove Result (1) we devise a technique that allows us to construct a morph in which each morphing step modifies either only the x-coordinates or only the y-coordinates of the vertices. Result (2) builds on the techniques in [2] and leverages on the arrangement of low-degree vertices in upward planar drawings in order to morph maximal plane st-graphs. We then exploit such morphs for general plane st-graphs. In order to prove Results (3) and (4) we use an inductive technique for gradually reducing the geometric differences between $\varGamma _0$ and $\varGamma _1$.

The paper is organized as follows. In Sect. 2 we introduce preliminary definitions and notation. In Sect. 3 we prove a lower bound on the number of morphing steps that might be required by an upward planar morph and we present a technique for constructing upward planar morphs with few morphing steps. In Sect. 4 we study upward planar morphs of plane st-graphs. In Sect. 5 we study upward planar morphs of general upward plane graphs. Finally, in Sect. 6 we present conclusions and open problems.

2 Preliminaries

We assume familiarity with graph drawing [18] and related concepts.

2.1 Graph Drawings

In a drawing of a graph vertices are represented by distinct points of the plane and edges are represented by Jordan arcs connecting the points representing their end-vertices. In a straight-line drawing the edges are represented by straight-line segments. Let $\varGamma$ be a drawing of a graph G and let H be a subgraph of G. We denote by $\varGamma [H]$ the restriction of $\varGamma$ to the vertices and edges of H. The following remark will simplify the reading hereafter.

Remark 1

In this paper we only consider straight-line drawings. Thus, where it leads to no confusion, we will omit the term “straight-line”.

2.2 Planar Drawings, Graphs, and Embeddings

A drawing of a graph is planar if no two edges intersect. A graph is planar if it admits a planar drawing. A planar drawing partitions the plane into topologically connected regions, called faces. The unique unbounded face is the outer face, whereas the remaining faces are the inner faces. Two planar drawings of a connected graph are topologically equivalent if they have the same circular order of the edges around each vertex and the same cycle bounding the outer face. A planar embedding is an equivalence class of topologically-equivalent planar drawings. A plane graph is a planar graph equipped with a planar embedding. In a planar straight-line drawing an internal face (the outer face) is strictly convex if its angles are all smaller (greater) than $\pi$. A planar straight-line drawing is strictly convex if each face is strictly convex.

A y-assignment $y_G: V(G) \rightarrow {\mathbb{R}}$ is an assignment of reals to the vertices of a graph G. A drawing $\varGamma$ of G satisfies $y_G$ if the y-coordinate in $\varGamma$ of each vertex $v \in V(G)$ is $y_G(v)$. An x-assignment $x_G$ for the vertices of G is defined analogously. A drawing $\varGamma$ of G induces a y-assignment and x-assignment for the vertices of G such that each vertex is assigned with its y-coordinate and with its x-coordinate in $\varGamma$, respectively.

2.3 Connectivity

A k-cut in a connected graph G is a set of k vertices whose removal disconnects G. A graph is k-connected if it does not contain any $(k-1)$-cut; 2-connected and 3-connected graphs are also called biconnected and triconnected graphs, respectively. The maximal biconnected subgraphs of a graph are called blocks. A biconnected plane graph G is internally 3-connected if, for every 2-cut $\{u,v\}$, u and v are incident to the outer face of G and each connected component of the graph $G - \{u,v\}$ contains a vertex incident to the outer face of G. The degree of a vertex in a graph is the number of edges incident to it. Clearly, a k-connected graph has minimum degree k.

2.4 Directed Graphs

In a directed graph G we denote by uv an edge directed from a vertex u to a vertex v; then v is a successor of u, and u is a predecessor of v. A source (resp. sink) of G is a vertex with no incoming edge (resp. with no outgoing edge). A directed path consists of the edges $u_iu_{i+1}$, for $i=1,\dots ,n-1$. A directed cycle consists of the edges $u_iu_{i+1}$, for $i=1,\dots ,n$, where $u_{n+1}=u_1$. A graph without directed cycles is acyclic. A transitive edge in a directed graph G is an edge uv such that G contains a directed path from u to v different from the edge uv. A reduced graph is a directed graph that does not contain any transitive edges. Whenever we do not know or are not interested in the orientation of an edge connecting two vertices u and v, we denote it by (u, v). The underlying graph of a directed graph G is the undirected graph obtained from G by omitting the directions from its edges. In this work, when talking about the connectivity of a directed graph, we refer to the connectivity of its underlying graph. A topological ordering of an n-vertex acyclic graph $G=(V,E)$ is a numbering $\pi : V \rightarrow \{1,2,\dots ,n\}$ of the vertices of G such that, for each edge $uv \in E$, we have $\pi (u) < \pi (v)$.

2.5 Upward Planar Drawings, Embeddings, and Morphs

A drawing of a directed graph is upward planar if it is planar and each edge uv is drawn as a curve monotonically increasing in the y-direction from u to v. A directed graph is upward planar if it admits an upward planar drawing.

Consider an upward planar (straight-line) drawing $\varGamma$ of a directed graph G and consider a vertex v of G. The list ${\mathcal{S}}(v)=[w_1,\dots ,w_k]$ contains the successors of v in “left-to-right order”. That is, consider the horizontal ray $\ell$ originating at v and directed leftwards; rotate $\ell$ around v in clockwise direction until it becomes again horizontal, and append each vertex $w_i$ to ${\mathcal{S}}(v)$ when $\ell$ overlaps with the edge $(v,w_i)$. The list ${\mathcal{P}}(v)=[z_1,\dots ,z_l]$ of the predecessors of v is defined similarly. Then two upward planar drawings of a connected directed graph are topologically equivalent if they have the same lists ${\mathcal{S}}(v)$ and ${\mathcal{P}}(v)$ for each vertex v. An upward planar embedding is an equivalence class of topologically-equivalent upward planar drawings. An upward plane graph is an upward planar graph equipped with an upward planar embedding. If a vertex v in an upward planar graph G is neither a source nor a sink, then a planar embedding of G determines ${\mathcal{S}}(v)$ and ${\mathcal{P}}(v)$. However, if v is a source or a sink, then different upward planar drawings might have different lists ${\mathcal{S}}(v)$ or ${\mathcal{P}}(v)$, respectively. In fact, two upward planar drawings of an upward planar graph G might not have the same upward planar embedding although the underlying graph of G has the same planar embedding in the two drawings; see, for example, Fig. 1.

Fig. 1

Two upward planar drawings of the same directed graph G (whose underlying graph is a simple cycle) with the same planar embedding but with different upward planar embeddings. The angles labeled large are gray. Observe that $\mathcal{S}(v_8)=[v_1,v_7]$ in a, while ${\mathcal{S}}(v_8)=[v_7,v_1]$ in b

For biconnected upward planar graphs a different, and yet equivalent, notion of upward planar embedding exists; this is described in the following. Consider an upward planar (straight-line) drawing $\varGamma$ of a biconnected upward planar graph G. Let u, v, and w be three distinct vertices that appear consecutively and in this clockwise order along the boundary of a face f of G; note that, since G is biconnected, f is delimited by a simple cycle. We denote by $\angle (u,v,w)$ the angle formed by the edges (u, v) and (v, w) at v in the interior of f. We say that v is a sink-switch (a source-switch) of f if the orientations of the edges (u, v) and (v, w) in G are uv and wv (vu and vw, respectively). Further, we say that v is a switch of f if it is either a sink-switch or a source-switch of f, and v is a switch of G if it is a switch of some face of G. Two switches u and v of a face f are clockwise (counter-clockwise) consecutive if traversing f clockwise (counter-clockwise) no switch is encountered in between u and v. The drawing $\varGamma$ determines a large-angle assignment, that is, a labeling, for each face f and each three clockwise consecutive vertices u, v, and w of f such that v is a switch of f, of the corresponding angle $\angle (u,v,w)$ as large, if it is larger than $\pi$ in $\varGamma$, or small, it is smaller than $\pi$ in $\varGamma$ [10]. Two upward planar drawings of a biconnected upward planar graph G are then say to be topologically equivalent if they have the same planar embedding and the same large-angle assignment. From this notion of topological equivalence, the ones of upward planar embedding and upward plane graph can be introduced as before; again, the formerly introduced notions coincide with the just introduced ones for upward planar graphs with biconnected underlying graphs (in fact, this correspondence between the two notions could be stated for all upward planar graphs, however the definition of clockwise consecutive switches we introduced is ambiguous for upward planar graphs whose underlying graph is not biconnected). A combinatorial characterization of the large-angle assignments that correspond to upward planar embeddings is given in [10].

Whenever we talk about an upward planar drawing of an upward plane graph G, we always assume, even when not explicitly stated, that the drawing respects the upward planar embedding associated to G. Further, whenever we talk about a subgraph H of an upward plane graph G, we always assume, even when not explicitly stated, that H is associated with the upward planar embedding obtained from the one associated to G by removing vertices and edges not in H.

Let $\varGamma _0$ and $\varGamma _1$ be two upward planar drawings of an upward plane graph G. An upward planar morph is a continuous transformation from $\varGamma _0$ to $\varGamma _1$ indexed by time $t \in [0,1]$ in which the drawing $\varGamma _t$ at each time $t \in [0,1]$ is upward planar. We remark that each drawing $\varGamma _t$ has to respect the upward planar embedding associated to G; in particular, since $\varGamma _0$ and $\varGamma _1$ respect the upward planar embedding associated to G, they are topologically equivalent. Observe that the condition that $\varGamma _0$ and $\varGamma _1$ are topologically equivalent is necessary for an upward planar morph between them to exist.

Fig. 2

An upward planar drawing of a plane st-graph. An st-face f is shaded gray; the left and the right boundary of f are red and blue, respectively (Color figure online)

2.6 Plane st-graphs

A plane st-graph is an upward plane graph with a single source s and a single sink t, and with an upward planar embedding in which s and t are incident to the outer face. Refer to Fig. 2. A plane st-graph always admits an upward planar straight-line drawing [19]; in fact, since any upward plane graph can be augmented to a plane st-graph [19], this result also extends to all upward plane graphs. A cycle in an upward plane graph is an st-cycle if it consists of two directed paths. A face f of an upward plane graph is an st-face if it is delimited by an st-cycle; the directed paths delimiting an st-face f are called left and right boundary, where the edge of the left boundary incident to the source-switch $s_f$ of f (to the sink-switch $t_f$ of f) immediately precedes the edge of the right boundary incident to $s_f$ (resp. to $t_f$) in the clockwise order of the edges incident to $s_f$ (resp. in the counter-clockwise order of the edges incident to $t_f$). The following is well-known.

Lemma 1

An upward plane graph is a plane st-graph iff all its faces are st-faces.

3 Slow Morphs and Fast Morphs

In this section we first show that “slow” upward planar morphs are sometimes necessary, i.e., there exist pairs of upward planar drawings that require a linear number of steps in order to be morphed into one another. Then we devise techniques for constructing “fast” upward planar morphs, i.e., upward planar morphs with a constant number of steps.

We start by proving the following lower bound.

Fig. 3

Illustration for Theorem 1. a P; b $\varGamma _0$; and c $\varGamma _1$. For the sake of readability, $\varGamma _0$ and $\varGamma _1$ have curved edges. However, the x-coordinates of the vertices can be slightly perturbed in order to make $\varGamma _0$ and $\varGamma _1$ straight-line

Theorem 1

There exist two upward planar straight-line drawings of an n -vertex upward plane path such that any upward planar morph between them consists of $\varOmega (n)$ steps.

Proof

Assume, for the sake of simplicity, that n is even, and let $n=2k$. Consider the n-vertex upward plane path P defined as follows (refer to Fig. 3a). The path P contains vertices $u_i$ and $v_i$, for $i=1,\dots ,k$, and directed edges $u_iv_i$, for $i=1,\dots ,k$, and $u_{i+1}v_i$, for $i=1,\dots ,k-1$. Clearly, P has a unique planar embedding ${\mathcal{E}}$; we fix the upward planar embedding of P so that ${\mathcal{S}}(u_i)=[v_i,v_{i-1}]$, for $i=2,\dots ,k$, and so that ${\mathcal{P}}(v_i)=[u_i,u_{i+1}]$, for $i=1,\dots ,k-1$.

Let $\varGamma _0$ and $\varGamma _1$ be two upward planar straight-line drawings of P in which the bottom-to-top order of the vertices is $u_1, \dots ,u_k,v_k,\dots ,v_1$ (see Fig. 3b) and $u_k, \dots ,u_1,v_1,\dots ,v_k$ (see Fig. 3c), respectively. Note that, by the upward planarity of $\varGamma _0$, the edge $u_iv_i$ has the edge $u_{i+1}v_{i+1}$ to its right in $\varGamma _0$, for $i=1,\dots ,k-1$, and the edge $u_{i+1}v_i$ has the edge $u_{i+2}v_{i+1}$ to its left in $\varGamma _0$, for $i=1,\dots ,k-2$. Let $\langle \varGamma _0 = \varLambda _1,\varLambda _2,\dots ,\varLambda _{h+1}=\varGamma _1 \rangle$ be any upward planar morph from $\varGamma _0$ to $\varGamma _1$ that consists of h morphing steps. We have the following.

Claim 1.1 For each $j=1,2,\dots ,\min \{h+1,k-1\}$, we have that:

• (a) the vertices $u_{j},u_{j+1},\dots ,u_{k-1},u_k,v_k,v_{k-1},\dots ,v_{j+1},v_j$ appear in this bottom-to-top order in $\varLambda _{j}$;

• (b) for $i=j,\dots ,k-1$, the edge $u_iv_i$ has the edge $u_{i+1}v_{i+1}$ to its right; and

• (c) for $i=j,\dots ,k-2$, the edge $u_{i+1}v_i$ has the edge $u_{i+2}v_{i+1}$ to its left.

Proof of the claim We prove the statement by induction on j. The statement is trivial for $j=1$, by the definition of $\varGamma _0 = \varLambda _1$.

Consider now any $j>1$. By induction, $\varLambda _{j-1}$ satisfies Properties (a)–(c).

Suppose, for a contradiction, that there exists an index $i\in \{j,j+1,\dots ,k-1\}$ such that $u_{i+1}$ lies below $u_i$ in $\varLambda _{j}$. The upward planarity of $\varLambda _{j-1}$ and $\varLambda _{j}$ implies that $v_i$ and $v_{i-1}$ both lie above $u_i$, both in $\varLambda _{j-1}$ and $\varLambda _{j}$. Further, $u_{i+1}$ lies below $v_i$ and $v_{i-1}$, both in $\varLambda _{j-1}$ and $\varLambda _{j}$; this comes from Property (a) of $\varLambda _{j-1}$ and from the assumption that $u_{i+1}$ lies below $u_i$ in $\varLambda _{j}$. Then $u_{i+1}$ lies below the horizontal line through the lowest of $v_i$ and $v_{i-1}$ throughout the linear morph $\langle \varLambda _{j-1},\varLambda _j\rangle$. By Properties (b) and (c) of $\varLambda _{j-1}$, the vertex $u_{i+1}$ lies in $\varLambda _{j-1}$ inside the bounded region of the plane delimited by the edge $u_iv_i$, by the edge $u_iv_{i-1}$, and by the horizontal line through the lowest of $v_i$ and $v_{i-1}$. However, by the assumption that $u_{i+1}$ lies below $u_i$ in $\varLambda _{j}$, we have that $u_{i+1}$ lies outside the same region in $\varLambda _{j}$. Since $u_{i+1}$ does not cross the horizontal line through the lowest of $v_i$ and $v_{i-1}$ throughout the linear morph $\langle \varLambda _{j-1},\varLambda _j\rangle$, it follows that $u_{i+1}$ crosses $u_iv_i$ or $u_iv_{i-1}$ during $\langle \varLambda _{j-1},\varLambda _j\rangle$, a contradiction.

An analogous proof shows that $v_{i+1}$ lies below $v_i$ in $\varLambda _{j}$, for $i=j,j+1,\dots ,k-1$. Property (a) for $\varLambda _{j}$ follows. Properties (b) and (c) follow by Property (a) and by the upward planarity of $\varLambda _{j}$. This concludes the proof of the claim. $\square$

By Claim 1.1 and since $u_k,u_{k-1}$ appear in this bottom-to-top order in $\varGamma _1=\varLambda _{h+1}$, we have that $h+1>k-1$, hence $h \in \varOmega (n)$. $\square$

We remark that the proof of Theorem 1 is similar in spirit to the one, presented in [2], to show that a linear number of steps may sometimes be necessary in order to morph two planar drawings of the same path into one another. In particular, both the proof in [2] and the proof of Theorem 1 exploit a starting “spiral-like” drawing of a path; while the proof in [2] requires the morph to unwind the drawing so to eventually become straight, the proof of Theorem 1 requires the morph to change the bottom-to-top order of the vertices while preserving the spirality of the drawing.

We now establish a tool that will allow us to design algorithms for morphing upward planar drawings with few morphing steps. Consider two planar straight-line drawings $\varGamma '$ and $\varGamma ''$ of a plane graph G inducing the same y-assignment. Since the drawings are straight-line and have the same y-assignment, a horizontal line $\ell$ intersects a vertex or an edge of G in $\varGamma '$ if and only if it intersects the same vertex or edge in $\varGamma ''$. We say that $\varGamma '$ and $\varGamma ''$ are left-to-right equivalent if, for any horizontal line $\ell$, for any vertex or edge $\alpha$ of G, and for any vertex or edge $\beta$ of G such that $\ell$ intersects both $\alpha$ and $\beta$ (in $\varGamma '$ and in $\varGamma ''$), we have that the intersection of $\alpha$ with $\ell$ and the intersection of $\beta$ with $\ell$ are in the same left-to-right order both in $\varGamma '$ as in $\varGamma ''$. The definition of bottom-to-top equivalent drawings is analogous (where we assume that $\varGamma '$ and $\varGamma ''$ are planar straight-line drawings inducing the same x-assignment). We have the following.

Lemma 2

Any two upward planar drawings $\varGamma '$and $\varGamma ''$of a plane st-graph G inducing the same y-assignment are left-to-right equivalent.

Proof

Since G is a plane st-graph, the drawings $\varGamma '$ and $\varGamma ''$ have the same faces. By Lemma 1 such faces are st-faces. Also, every horizontal line $\ell$ crosses an st-face f at most twice, and the left-to-right order of these crossings along $\ell$ is the same in $\varGamma '$ and $\varGamma ''$ because the left and right boundaries of f are the same in $\varGamma '$ and $\varGamma ''$, given that $\varGamma '$ and $\varGamma ''$ are topologically equivalent. $\square$

Lemma 3 is due to [2]. We extend it in Lemma 4.

Lemma 3

(Alamdari et al. [2], Corollary 7.2) Consider a unidirectional morph acting on points p, q, and r. If p is on one side of the oriented line through ${\overline{qr}}$at the beginning and at the end of the morph, then p is on the same side of the oriented line through ${\overline{qr}}$throughout the morph.

Lemma 4

Let $\varGamma '$and $\varGamma ''$ be two left-to-right or bottom-to-top equivalent planar drawings of a plane graph. Then the linear morph ${\mathcal{M}}$from $\varGamma '$to $\varGamma ''$is unidirectional and planar.

Proof

Since $\varGamma '$ and $\varGamma ''$ have the same y-assignment (x-assignment), given that they are left-to-right (bottom-to-top) equivalent, it follows that all the vertices move along horizontal (vertical) trajectories. Thus, ${\mathcal{M}}$ is unidirectional. Also, since $\varGamma '$ and $\varGamma ''$ are left-to-right (bottom-to-top) equivalent, each horizontal (vertical) line crosses the same sequence of vertices and edges in both $\varGamma '$ and $\varGamma ''$. Thus, by Lemma 3, ${\mathcal{M}}$ is planar. $\square$

Lemma 4 allows us to devise a simple morphing technique between any two upward planar drawings $\varGamma _0$ and $\varGamma _1$ of the same upward plane graph G, when a pair of upward planar drawings of G with special properties can be computed. We say that the pair $(\varGamma _0,\varGamma _1)$ is an hvh-pair if there exist upward planar drawings $\varGamma '_0$ and $\varGamma '_1$ of G such that: (1) $\varGamma _0$ and $\varGamma '_0$ are left-to-right equivalent, (2) $\varGamma '_0$ and $\varGamma '_1$ are bottom-to-top equivalent, and (3) $\varGamma '_1$ and $\varGamma _1$ are left-to-right equivalent. Our morphing tool is expressed by the following lemma.

Lemma 5

(Fast morph) Let $(\varGamma _0,\varGamma _1)$be an hvh-pair of upward planar drawings of an upward plane graph G. There exists a 3-step upward planar morph from $\varGamma _0$to $\varGamma _1$.

Proof

By hypothesis there exist drawings $\varGamma '_0$ and $\varGamma '_1$ of G satisfying Conditions (1), (2), and (3) of the definition of an hvh-pair. By Lemma 4, ${\mathcal{M}}_1 = \langle \varGamma _0, \varGamma '_0 \rangle$, ${\mathcal{M}}_2 = \langle \varGamma '_0, \varGamma '_1 \rangle$, and ${\mathcal{M}}_3 = \langle \varGamma '_1, \varGamma _1 \rangle$ are planar linear morphs. Therefore, ${\mathcal{M}} = \langle \varGamma _0, \varGamma '_0, \varGamma '_1, \varGamma _1 \rangle$ is a 3-step planar morph from $\varGamma _0$ to $\varGamma _1$. In order to prove that ${\mathcal{M}}$ is an upward planar morph, we need to show that each linear morph ${\mathcal{M}}_i$ is an upward planar morph. To this aim, we only need to prove that no edge changes its orientation during ${\mathcal{M}}_i$, for $i=1,2,3$. This is trivially true for $\mathcal{M}_1$ (for ${\mathcal{M}}_3$) since $\varGamma _0$ and $\varGamma '_0$ ($\varGamma _1$ and $\varGamma '_1$) induce the same y-assignment.

Fig. 4

Illustration for the proof of Lemma 5. The edge uv does not change its orientation during ${\mathcal{M}}_2$

We now prove that no directed edge uv changes its orientation during ${\mathcal{M}}_2$; refer to Fig. 4. By Condition (2) of the definition of an hvh-pair, the x-coordinate of u is the same in $\varGamma '_0$ and in $\varGamma '_1$, hence it is the same throughout ${\mathcal{M}}_2$. Denote by $x'$ such x-coordinate. The y-coordinate of u might be different in $\varGamma '_0$ and in $\varGamma '_1$; denote by $y'_0$ and $y'_1$ such coordinates, respectively. Consider a point r that moves (at uniform speed along a straight-line trajectory) during $\mathcal{M}_2$ from $(x'+1,y'_0)$ in $\varGamma _0$ to $(x'+1,y'_1)$ in $\varGamma _1$. Note that r moves along a vertical trajectory, hence the movement of r and ${\mathcal{M}}_2$ define a unidirectional morph. Also observe that the straight-line segment ${\overline{ur}}$ is horizontal throughout ${\mathcal{M}}_2$; further, v is above the horizontal line through ${\overline{ur}}$ both in $\varGamma '_0$ and in $\varGamma '_1$, by the upward planarity of $\varGamma _0$ and $\varGamma _1$ and by Conditions (1) and (3) of the definition of an hvh-pair. By Lemma 3 with $p=v$, $q=u$, and $r=r$ we have that the y-coordinate of v is greater than the y-coordinate of u throughout ${\mathcal{M}}_2$. Hence, ${\mathcal{M}}_2$ is an upward planar morph. $\square$

We remark that, in each of the 3 morphing steps of the algorithm given in Lemma 5, either all the vertices move horizontally or they all move vertically. Such horizontal or vertical morphing steps have also been used in [26].

The next lemma will allow us to restrict our attention to biconnected graphs.

Lemma 6

Let $\varGamma _0$and $\varGamma _1$be two upward planar drawings of an n-vertex upward plane graph G whose underlying graph is connected. There exist an upward plane graph $G'$and two upward planar drawings $\varGamma '_0$and $\varGamma '_1$of $G'$such that:

• $G'$has O(n) vertices;

• $G'$is a supergraph of G;

• the underlying graph of $G'$is biconnected;

• $\varGamma '_0[G]=\varGamma _0$and $\varGamma '_1[G]=\varGamma _1$; and

• if G is reduced or an st-graph, then so is $G'$.

Proof

Initialize $G'=G$, $\varGamma '_0=\varGamma _0$, and $\varGamma '_1=\varGamma _1$. Consider a cutvertex v of $G'$. Let u and w be two neighbors of v belonging to different blocks of $G'$ that are consecutive in the circular order of the neighbors of v. By relabeling u and w, we may assume that one of the following holds true:

• if u and w are both successors of v, then the edge vw immediately follows the edge vu in the clockwise order of the edges incident to v (see Fig. 5a);

• if u and w are both predecessors of v, then the edge wv immediately precedes the edge uv in the clockwise order of the edges incident to v (see Fig. 5b); or

• u is a successor of v, w is a predecessor of v, and the edge wv immediately follows the edge vu in the clockwise order of the edges incident to v (see Fig. 5c).

Fig. 5

Illustration for Lemma 6. The vertices u and w belong to two blocks $\beta _u$ and $\beta _w$, respectively, both containing the cut-vertex v

Denote by f the face that is to the right of the edge (u, v) when traversing such an edge according to its orientation. Note that the edge (v, w) is also incident to f. We add to $G'$ a new vertex $v'$ inside f; further, we add to $G'$ two directed edges connecting $v'$ with u and w inside f. These edges are directed as the edges connecting v with u and w, respectively; that is, we add to $G'$ either the directed edge $uv'$, if $uv \in E(G')$, or the directed edge $v'u$, if $vu \in E(G')$, and either the directed edge $wv'$, if $wv \in E(G')$, or the directed edge $v'w$, if $vw \in E(G')$.

The described augmentation does not introduce any transitive edges. Further, no edge that was already in $G'$ before the augmentation becomes transitive after the augmentation; this is because the edge (u, w) does not belong to $G'$, as u and w belong to distinct blocks of $G'$. Hence, $G'$ remains reduced if it was so.

In the case illustrated in Fig. 5a (in Fig. 5b), each of the blocks $\beta _u$ and $\beta _w$ of $G'$ containing u and w before the augmentation contains a distinct sink of $G'$ (resp. a distinct source of $G'$), hence $G'$ is not an st-graph before the augmentation. In the case illustrated in Fig. 5c, it might be that $G'$ is an st-graph before the augmentation. Note that there are only two faces of the augmented graph $G'$ that do not belong to $G'$ before the augmentation. One of them is delimited by the directed paths wvu and $wv'u$, hence it is an st-face; the other one is obtained from f by replacing the directed path wvu with the directed path $wv'u$, hence it is an st-face as long as f is. It follows that, if $G'$ is an st-graph before the augmentation, then it remains an st-graph after the augmentation.

We now describe how to insert $v'$ and its incident edges into $\varGamma '_0$ and $\varGamma '_1$. By standard continuity arguments, like the ones used in the proof of Fáry’s theorem [21], we have that, for $i=0,1$, there exists a sufficiently small value $\epsilon _i > 0$ such that the disk $d_i$ with radius $\epsilon _i$ centered at v in $\varGamma '_i$ contains no vertex other than v and is not traversed by any edge other than those incident to v. We place $v'$ at distance $\epsilon < \epsilon _0,\epsilon _1$ from v inside f, as illustrated in Fig. 5a–c; in particular, $v'$ is placed in the circular sector of $d_i$ delimited by (u, v) and (w, v). By selecting a sufficiently small value for $\epsilon$, the edges $(u,v')$ and $(w,v')$ can be drawn as straight-line segments that do not intersect any edge of $G'$. Further, if $\epsilon$ is sufficiently small, then the y-coordinate of u (the y-coordinate of w) is smaller than the one of $v'$ if and only if it is smaller than the one of v, hence the straight-line segments representing the edges $(u,v')$ and $(w,v')$ monotonically increase in the y-direction from their sources to their sinks. The upward planarity of the drawings $\varGamma '_0$ and $\varGamma '_1$ of the augmented graph $G'$ follows. Note that after the augmentation we have $\varGamma '_0[G]= \varGamma _0$ and $\varGamma '_1[G]= \varGamma _0$. This is because the same equalities were satisfied before the augmentation and since the drawings of $G'$ before the augmentation were not altered during the augmentation.

Since the graph $G'$ after the augmentation contains one block less than before the augmentation, the repetition of this argument results in a biconnected graph $G'$. This concludes the proof of the lemma. $\square$

4 Plane st-graphs

In this section we present algorithms for constructing upward planar morphs between upward planar drawings of plane st-graphs.

4.1 Reduced Plane st-graphs

We first consider plane st-graphs without transitive edges. We have the following.

Lemma 7

Any two upward planar drawings of a reduced plane st-graph G form an hvh-pair.

Proof

By Lemma 6 we can assume that the reduced plane st-graph G is biconnected. Let $\varGamma _0$ and $\varGamma _1$ be any two upward planar drawings of G. We show that $\varGamma _0$ and $\varGamma _1$ form an hvh-pair by exhibiting two upward planar drawings $\varGamma '_0$ and $\varGamma '_1$ of G that satisfy Conditions (1), (2), and (3) of the definition of an hvh-pair.

We construct drawings $\varGamma '_0$ and $\varGamma '_1$ as follows (refer to Figs. 6 and 7). Consider the weak dual multi-graph D of G, which is defined as follows. The multi-graph D has a vertex $v_f$ for each internal face f of G and a directed edge $v_f v_g$ if the faces f and g of G share an edge e in G and f lies to the left of g when traversing e according to its orientation. The concept of weak dual multi-graph has been used, e.g., in [29, 33, 33]. Observe that D is acyclic [32]. We now present a structural decomposition of G guided by D which has been used, e.g., in [22, 27]. Let ${\mathcal{T}}=\{v_1, \dots , v_k\}$ be a topological ordering of the vertices of D and let $P_0$ be the left boundary of the outer face of G. The ordering ${\mathcal{T}}$ defines a sequence $P_1$, $P_2$, ..., $P_k$ of directed paths such that, for each $i=1,\dots ,k$, the path $P_j$ is the right boundary of the face of G corresponding to the vertex $v_j$ of D. For $j=1,\dots ,k$, the graph $G_j=\bigcup _{i=0}^j P_i$ is a plane st-graph which is obtained by attaching the directed path $P_{j}$ to two non-adjacent vertices on the right boundary of the outer face of $G_{j-1}$; further, $G_k=G$. Note that, since G is a reduced plane st-graph, no path $P_j$ consists of a single edge.

The drawings $\varGamma '_0$ and $\varGamma '_1$ are simultaneously and iteratively constructed by adding, for $j=1,\dots ,k$, the path $P_j$ to the already constructed drawings $\varGamma '_0$ and $\varGamma '_1$ of $G_{j-1}$. Note that, after $P_j$ has been drawn in $\varGamma '_0$ and $\varGamma '_1$, the right boundary of the outer face of $G_{j}$ is a directed path, hence it is represented by a y-monotone curve in both $\varGamma '_0$ and $\varGamma '_1$.

Fig. 6

Illustration for the proof of Lemma 7. a The drawing $\varGamma '_i$ of $G_0=P_0$. b The drawing $\varGamma '_i$ of $G_1$

Fig. 7

Illustration for the proof of Lemma 7. Computation of the points $a_i$ and $b_i$ in $\varGamma '_i$ for the cases $\ell =2$ (a) and $\ell >2$ (b), respectively. Drawing of the path $P_j$ for the cases $\ell =2$ (c) and $\ell >2$ (d)

For $i=0,1$, we denote by $y_i(v)$ the y-coordinate of a vertex v in $\varGamma _i$.

We obtain drawings $\varGamma '_0$ and $\varGamma '_1$ of $G_0 = P_0$ by placing its vertices along the line $x=0$ at the y-coordinates they have in $\varGamma _0$ and $\varGamma _1$, respectively, and by drawing its edges as straight-line segments (see Fig. 6a). It is easy to see that $\varGamma _0[G_0]$, $\varGamma '_0$, $\varGamma '_1$, and $\varGamma _1[G_0]$ fulfill Conditions (1)–(3) of the definition of an hvh-pair.

Suppose now that, for some $j\in \{1,\dots ,k\}$, the drawings $\varGamma '_0$ and $\varGamma '_1$ are upward planar straight-line drawings of $G_{j-1}$ such that $\varGamma _0[G_{j-1}]$, $\varGamma '_0$, $\varGamma '_1$, and $\varGamma _1[G_{j-1}]$ fulfill Conditions (1)–(3) of the definition of an hvh-pair.

We show how to add the path $P_j= u_0 u_1 \dots u_{\ell -1} u_\ell$ to both $\varGamma '_0$ and $\varGamma '_1$ so that the resulting drawings together with $\varGamma _0[G_{j}]$ and $\varGamma _1[G_{j}]$ fulfill Conditions (1)–(3) of the definition of an hvh-pair. Note that $u_0$ and $u_\ell$ belong to the right boundary of the outer face of $G_{j-1}$, hence they are already present in $\varGamma '_0$ and $\varGamma '_1$. Since all the edges of $P_j$ are going to be drawn as straight-line segments, it suffices to show how to draw the internal vertices of $P_j$ in $\varGamma '_0$ and $\varGamma '_1$. For $i=0,1$, we assign to the internal vertices of $P_j$ in $\varGamma '_i$ the same y-coordinates they have in $\varGamma _i$. Also, we assign to all such vertices, in both drawings, the same x-coordinate $x^*_j$, which has a “sufficiently large” value determined as follows.

If $j=1$, then we set $x^*_j=1$ (see Fig. 6b).

If $j>1$, then we proceed as follows. Refer to Fig. 7.

For $i=0,1$, let $\rho _i(u_0)$ be a ray emanating from $u_0$ with positive slope, directed rightwards, not intersecting $\varGamma '_i$, except at $u_0$, and such that the intersection point $a_i$ of $\rho _i(u_0)$ with the horizontal line $y= y_i(u_1)$ lies to the right of every vertex in $\varGamma '_i$. Analogously, for $i=0,1$, let $\rho _i(u_\ell )$ be a ray emanating from $u_\ell$ with negative slope, directed rightwards, not intersecting $\varGamma '_i$, except at $u_\ell$, and such that the intersection point $b_i$ of $\rho _i(u_\ell )$ with the horizontal line $y= y_i(u_{\ell -1})$ lies to the right of every vertex in $\varGamma '_i$. Refer to Fig. 7a, b for the cases in which $\ell =2$ and $\ell >2$, respectively. Observe that $u_1$ and $u_{\ell -1}$ coincide if $P_j$ is a path of length 2, i.e., if $\ell = 2$. We set $x^*_j$ as the maximum of the x-coordinates of $a_0$, $b_0$, $a_1$, and $b_1$.

The obtained drawings $\varGamma '_0$ and $\varGamma '_1$ of $G_j$ are planar, as the slopes of the straight-line segments representing the edge $u_0 u_1$ in $\varGamma '_0$ and $\varGamma '_1$ are smaller than or equal to those of $\rho _0(u_0)$ and $\rho _1(u_0)$, respectively, as the slopes of the straight-line segments representing the edge $u_{\ell -1} u_\ell$ in $\varGamma '_0$ and $\varGamma '_1$ are larger than or equal to those of $\rho _0(u_\ell )$ and $\rho _1(u_\ell )$, respectively, and as the vertical line $x=x^*_j$ lies to the right of all the vertices of $G_{j-1}$ both in $\varGamma '_0$ and in $\varGamma '_1$. The drawings $\varGamma '_0$ and $\varGamma '_1$ are upward, given that the vertices of $G_j$ have the same y-coordinates they have in $\varGamma _0$ and $\varGamma _1$, respectively, and given that $\varGamma _0$ and $\varGamma _1$ are upward drawings.

In order to conclude the proof, we show that the obtained drawings, together with $\varGamma _0[G_j]$ and $\varGamma _1[G_j]$, fulfill Conditions (1)–(3) of the definition of an hvh-pair. Since ($\varGamma _0$,$\varGamma '_0$) and ($\varGamma _1$, $\varGamma '_1$) are pairs of upward planar drawings of $G_j$ inducing the same y-assignment, by Lemma 2, Conditions (1) and (3) hold true. In order to prove Condition (2), first recall that by construction $\varGamma '_0$ and $\varGamma '_1$ have the same x-assignment. Also, since all the intermediate vertices of any path $P_j$ are drawn on the vertical line $x=x^*_j$ in both $\varGamma '_0$ and $\varGamma '_1$, and the circular ordering of the edges around each vertex is the same in both $\varGamma '_0$ and $\varGamma '_1$, we have that the sequence of vertices and edges crossed by each vertical line in $\varGamma '_0$ and $\varGamma '_1$ is the same, thus implying Condition (2). $\square$

Combining Lemma 5 with Lemma 7 we obtain the following result.

Theorem 2

Let $\varGamma _0$and $\varGamma _1$be any two upward planar straight-line drawings of a reduced plane st-graph. There exists a 3-step upward planar morph from $\varGamma _0$to $\varGamma _1$.

4.2 General Plane st-graphs

We now turn our attention to general plane st-graphs. We restate here, in terms of plane st-graphs, a result by Hong and Nagamochi [24] that was originally formulated in terms of hierarchical plane (undirected) graphs.

Theorem 3

(Hong and Nagamochi [24], Theorem 8) Consider an internally 3-connected plane st-graph G and let $y_G$be a y-assignment for the vertices of G such that each vertex v is assigned a value $y_G(v)$that is greater than those assigned to its predecessors. There exists a strictly-convex upward planar drawing of G satisfying $y_G$.

We use Theorem 3 to prove the following lemma, which allows us to restrict our attention to maximal plane st-graphs.

Lemma 8

Let $\varGamma _0$and $\varGamma _1$be two upward planar drawings of an n-vertex plane st-graph G. Suppose that an algorithm ${\mathcal{A}}$exists that constructs an f(r)-step upward planar morph between any two upward planar drawings of an r-vertex maximal plane st-graph. Then, there exists an O(f(n))-step upward planar morph from $\varGamma _0$to $\varGamma _1$.

Proof

By Lemma 6, we can assume that G is biconnected.

We augment G to a maximal plane st-graph $G^*$ as follows (refer to Fig. 8a). For each internal face f of G we add to G: (1) a vertex $v_f$ into f, (2) a directed edge from the source-switch $s_f$ of f to $v_f$, and (3) directed edges from $v_f$ to every other vertex incident to f. We also add a vertex $v^*$ into the outer face of G, and add directed edges from $v^*$ to all the vertices incident to the outer face of G. The resulting graph $G^*$ is a maximal plane st-graph (and in particular it is internally-3-connected) and contains O(n) vertices.

Fig. 8

Illustration for the proof of Lemma 8. a A biconnected plane st-graph G (shown with black vertices and thick edges) and its augmentation to a maximal plane st-graph $G^*$ (by the addition of the white vertices and white-arrowed edges). b The construction of an upward planar drawing $\varGamma ^*_i$ of $G^*$ in which each vertex of $G^*$ that is also in G has the same y-coordinate as in $\varGamma _i$

Denote by $y^0_G$ the y-assignment for the vertices of G that is induced by $\varGamma _0$. We define a y-assignment $y^0_{G^*}$ for the vertices of $G^*$ by setting:

• $y^0_{G^*}(v)=y^0_{G}(v)$ for each vertex $v\in V(G)$;

• for each vertex $v_f$ of $G^*$ inserted into an internal face f of G, a value for $y^0_{G^*}(v_f)$ that is larger than $y^0_{G^*}(s_f)$ and smaller than $y^0_{G^*}(v)$, for every other vertex v incident to f; and

• for the vertex $v^*$ of $G^*$ inserted into the outer face of G, a value for $y^0_{G^*}(v^*)$ that is smaller than $y^0_{G^*}(v)$, for every vertex $v\ne v^*$ of $G^*$.

We similarly define a y-assignment $y^1_{G^*}$ for the vertices of $G^*$ using the y-coordinates of $\varGamma _1$.

Note that, for $i=0,1$, each vertex v of $G^*$ has been assigned a value $y^i_{G^*}$ that is greater than those assigned to its predecessors. We can hence use Theorem 3 to construct strictly-convex upward planar drawings $\varGamma ^*_0$ and $\varGamma ^*_1$ of $G^*$ satisfying $y^0_{G^*}$ and $y^1_{G^*}$, respectively (refer to Fig. 8b).

By Lemma 2 we have that the drawings $\varGamma ^*_0[G]$ and $\varGamma _0$ are left-to-right equivalent. Therefore, by Lemma 4, the linear morph ${\mathcal{M}}_0$ from $\varGamma _0$ to $\varGamma ^*_0[G]$ is planar. Such a morph is also upward since both $\varGamma _0$ and $\varGamma ^*_0[G]$ are upward planar and left-to-right equivalent. Analogously, the linear morph ${\mathcal{M}}_1$ from $\varGamma ^*_1[G]$ to $\varGamma _1$ is upward planar.

We now apply algorithm ${\mathcal{A}}$ to construct an f(n)-step upward planar morph from $\varGamma ^*_0$ to $\varGamma ^*_1$ and restrict such a morph to the vertices and edges of G to obtain an f(n)-step upward planar morph ${\mathcal{M}}_{01}$ from $\varGamma ^*_0[G]$ to $\varGamma ^*_1[G]$.

An upward planar morph ${\mathcal{M}}$ from $\varGamma _0$ to $\varGamma _1$ is finally obtained as the concatenation of ${\mathcal{M}}_0$, $\mathcal{M}_{01}$, and ${\mathcal{M}}_1$. The number of steps of ${\mathcal{M}}$ is equal to the number of steps of ${\mathcal{M}}_{01}$ plus two, hence it is in O(f(n)). This concludes the proof. $\square$

In the following we will present an algorithm that constructs an upward planar morph between two upward planar drawings of a maximal plane st-graph. Before doing so, we need to introduce one more tool. By polygon we mean a closed curve formed by straight-line segments. We say that a vertex of a polygon P sees a different vertex of P if the open straight-line segment between the two vertices lies in the interior of P. We also say that v sees P if it sees all the vertices of P that are not adjacent to v along P. We have the following.

Lemma 9

Let $\varGamma$be an upward planar drawing of an internally 3-connected plane st-graph G. There exists a strictly-convex upward planar drawing $\varGamma '$of G such that ${\mathcal{M}} = \langle \varGamma , \varGamma ' \rangle$is an upward planar morph.

Further, if v is incident to an internal face f of G and sees the polygon $P_f$bounding f in $\varGamma$, then v sees the polygon bounding f throughout ${\mathcal{M}}$.

Proof

Denote by $y_G$ the y-assignment for the vertices of G induced by $\varGamma$. By Theorem 3, there exists a strictly-convex upward planar drawing $\varGamma '$ of G satisfying $y_G$. Thus, by Lemma 2 and since G is a plane st-graph, we have that $\varGamma$ and $\varGamma '$ are left-to-right-equivalent drawings. By Lemma 4, the linear morph ${\mathcal{M}}$ from $\varGamma$ to $\varGamma '$ is planar. Since $\varGamma$ and $\varGamma '$ are upward and left-to-right equivalent, it follows that ${\mathcal{M}}$ is an upward planar morph.

Consider an internal face f of G and let v be any vertex incident to f that sees the polygon $P_f$ bounding f in $\varGamma$. Since the polygon $P'_f$ representing the boundary of f in $\varGamma '$ is strictly convex, v also sees $P'_f$. Augment G to an upward plane st-graph $G_*$ by introducing (suitably oriented) edges connecting v to the vertices incident to f that are not already adjacent to v; note that, by means of these edges, f has been split into triangular faces of $G_*$. Draw these edges in $\varGamma$ and $\varGamma '$ as straight-line segments, obtaining two upward planar drawings $\varGamma _*$ and $\varGamma _*'$ of $G_*$ (this is possible since v sees $P_f$ in $\varGamma$ and $P'_f$ in $\varGamma '$). Since $\varGamma _*$ and $\varGamma _*'$ are upward planar drawings of $G^*$ inducing the same y-assignment and since $G^*$ is a plane st-graph, they are left-to-right equivalent, by Lemma 2. Therefore, by Lemma 4, we have that the linear morph ${\mathcal{M}}_* = \langle \varGamma _*, \varGamma _*'\rangle$ is planar. Note that $\mathcal{M}_* = \langle \varGamma _*, \varGamma _*'\rangle$ coincides with ${\mathcal{M}} = \langle \varGamma , \varGamma ' \rangle$ when restricted to the vertices and edges of G. Hence, the open straight-line segments connecting v to the vertices incident to f that are not adjacent to v in G lie inside the polygon bounding f throughout ${\mathcal{M}}$. This implies that v sees the polygon bounding f throughout ${\mathcal{M}}$. $\square$

An internal vertex v of a maximal plane graph G is simple if the neighbors of v induce a cycle in the underlying graph of G. We have the following.

Lemma 10

Any maximal plane graph with at least four vertices contains a simple vertex of degree at most 5.

Proof

Consider any maximal plane graph G. By Euler’s formula, there exists at least one internal vertex v of G of degree at most 5. If v is simple, then we are done. Otherwise, G contains an edge between two non-consecutive neighbors w and z of v. Then the subgraph $G'$ of G induced by the vertices inside or on the boundary of the 3-cycle (v, w, z) is a maximal plane graph with at least four vertices, as it contains a neighbor of v different from w and z; further, $G'$ has less vertices than G. Hence, the same argument can now be repeated on $G'$; eventually, this leads to finding a simple vertex of degree at most 5. $\square$

Given two upward planar straight-line drawings $\varGamma _0$ and $\varGamma _1$ of a maximal plane st-graph G, our strategy for constructing an upward planar morph from $\varGamma _0$ to $\varGamma _1$ consists of the following steps:

• 1. we find a simple vertex v of G of degree at most 5;

• 2. we remove v and its incident edges from G, $\varGamma _0$, and $\varGamma _1$, obtaining upward planar drawings $\varGamma ^-_0$ and $\varGamma ^-_1$ of an upward plane graph $G^-$;

• 3. we triangulate $G^-$, $\varGamma ^-_0$, and $\varGamma ^-_1$ by inserting edges incident to a former neighbor u of v, obtaining upward planar drawings $\varGamma '_0$ and $\varGamma '_1$ of a maximal plane st-graph $G'$;

• 4. we apply induction in order to construct an upward planar morph ${\mathcal{M}}'$ from $\varGamma '_0$ to $\varGamma '_1$; and

• 5. we remove from ${\mathcal{M}}'$ the edges incident to u that are not in G and insert v and its incident edges in ${\mathcal{M}}'$, thus obtaining an upward planar morph from $\varGamma _0$ to $\varGamma _1$.

In order for this strategy to work, we need that u satisfies certain properties, which are expressed in the upcoming definition of distinguished neighbor; further, we need to perform one initial (and one final) upward planar morph so to convexify the polygon representing what will be called a characteristic cycle.

Let v be a simple vertex with degree at most 5 in a maximal plane st-graph G; this exists by Lemma 10. Let G(v) be the subgraph of G induced by v and its neighbors.

A predecessor u of v in G is a distinguished predecessor if u and v satisfy the following conditions: (a) for each predecessor w of v, there is a directed path in G(v) from w to v through u; (b) u is the only predecessor of v, if its degree is 3; and (c) v has at most two predecessors, if its degree is 4 or 5.

A successor u of v in G is a distinguished successor if u and v satisfy the following conditions: (a) for each successor w of v, there is a directed path in G(v) from v to w through u; (b) u is the only successor of v, if its degree is 3; and (c) v has at most two successors, if its degree is 4 or 5.

A neighbor of v is a distinguished neighbor if it is either a distinguished predecessor or successor of v. Examples of distinguished neighbors are in Fig. 9. We are going to exploit the following.

Fig. 9

Distinguished predecessors (enclosed by red squares), distinguished successors (enclosed by red circles), and characteristic cycles (filled yellow). Note that, in (e), (g), and (h), the vertex $s_2$ is not a distinguished successor of v; indeed, although for every successor w of v there is a directed path in G(v) from v to w through $s_2$, we have that v has more than two successors (Color figure online)

Lemma 11

Let v be a simple vertex with degree at most 5 in a maximal plane st-graph G. Then v has at most one distinguished predecessor, at most one distinguished successor, and at least one distinguished neighbor.

Proof

Suppose, for a contradiction, that v has (at least) two distinguished predecessors $u_1$ and $u_2$. Since $u_1$ is a distinguished predecessor of v and $u_2$ is a predecessor of v, it follows that G contains a directed path $u_2 \dots u_1 v$; further, since $u_2$ is a distinguished predecessor of v and $u_1$ is a predecessor of v, it follows that G contains a directed path $u_1 \dots u_2 v$. The union of these directed paths contains a directed cycle, a contradiction to the fact that G is an st-graph. It follows that v has at most one distinguished predecessor. An analogous argument proves that v has at most one distinguished successor.

Let P and S be the sets of predecessors and successors of v in G, respectively.

If the degree of v is 3, then either $|P|=1$ or $|S|=1$. In the former case the only predecessor of v is a distinguished predecessor of v, while in the latter case the only successor of v is a distinguished successor of v.

Assume next that the degree of v is 4 or 5. We prove that, if $|P|\le 2$, then v has at least one distinguished predecessor. If $|P|=1$, then the only predecessor of v is a distinguished predecessor of v. Further, if $|P|=2$, then let s and p be the two predecessors of v in G. Since G is maximal, it contains either the directed edge sp or the directed edge ps. In the former case p is a distinguished predecessor of v, while in the latter case s is a distinguished predecessor of v. An analogous proof shows that, if $|S|\le 2$, then v has at least one distinguished successor. This completes the proof, given that $|P|\le 2$ or $|S|\le 2$, since the degree of v is at most 5. $\square$

We define the characteristic cycle C(v) of the vertex v as follows. Let $c_G(v)$ be the subgraph of G induced by the neighbors of v. Since v is simple, the underlying graph of $c_G(v)$ is a cycle. If $c_G(v)$ is an st-cycle, as in Fig. 9a–d, then $C(v):=c_G(v)$; in particular, this is always the case if v has degree 3. Otherwise, $c_G(v)$ has two sources $s_1$ and $s_2$ and two sinks $t_1$ and $t_2$. Throughout the rest of this section, we always assume that, if $c_G(v)$ has two sources $s_1$ and $s_2$ and two sinks $t_1$ and $t_2$, then G contains the edges $s_1v$ and $vs_2$; indeed, the cases in which G contains the edges $s_2v$ and $vs_1$, or $t_1v$ and $vt_2$, or $t_2v$ and $vt_1$ are analogous. This assumption implies that v has at least three successors, namely $s_2$, $t_1$, and $t_2$, and hence no distinguished successor. Suppose also, w.l.o.g., that $s_1, t_1, s_2$, and $t_2$ appear in this clockwise order along $c_G(v)$. If v has degree 4, as in Fig. 9e, then C(v) is composed of the edges $s_1v$, $vs_2$, $s_2t_2$, and $s_1t_2$. Otherwise, v has degree 5, as in Fig. 9f–h. Let $v_1$ be the distinguished predecessor of v. The directed path $P_1 = v_1vs_2$ splits $c_G(v)$ into two paths $P_2$ and $P_3$ with length 2 and 3, respectively. Then C(v) is composed of $P_1$ and $P_3$. We have the following structural lemma.

Lemma 12

Let v be a simple vertex with degree at most 5 in a maximal plane st-graph G. The characteristic cycle C(v) is an st-cycle which contains all the distinguished neighbors of v. Further, all the vertices of $c_G(v)$not belonging to C(v) are adjacent to all the distinguished neighbors of v.

Proof

If $c_G(v)$ is an st-cycle, then by construction C(v) coincides with $c_G(v)$, hence C(v) is an st-cycle which contains all the neighbors (and in particular all the distinguished neighbors) of v, and there are no vertices of $c_G(v)$ not belonging to C(v). In the following we hence assume that $c_G(v)$ is not an st-cycle.

If v has degree 4, then by construction C(v) consists of two directed paths, namely $s_1vs_2t_2$ and $s_1t_2$, hence it is an st-cycle which contains the only distinguished neighbor (namely $s_1$) of v. The only vertex of $c_G(v)$ not belonging to C(v), namely $t_1$, is adjacent to $s_1$.

If v has degree 5, then observe that v is neither a source nor a sink of C(v), as C(v) contains the directed edges $v_1v$ and $vs_2$; further, $s_2$ is neither a source nor a sink of C(v), as C(v) contains the directed edge $vs_2$ and the directed edge of $P_3$ outgoing $s_2$. Since the underlying graph of C(v) is a cycle with 5 vertices, it follows that C(v) has one source and one sink, hence it is an st-cycle. Further, by construction C(v) contains $v_1$, hence it contains all the distinguished neighbors of v. Finally, the only vertex of $c_G(v)$ not belonging to C(v) is the internal vertex of $P_2$, which is adjacent to $v_1$. $\square$

Characteristic cycles are used in order to prove the following.

Lemma 13

Let v be a simple vertex with degree at most 5 in a maximal plane st-graph G. Let $\varGamma$be any upward planar drawing of G. There exists an upward planar morph $\langle \varGamma , \varGamma ' \rangle$, where in $\varGamma '$each of the distinguished neighbors of v sees the polygon representing $c_G(v)$.

Proof

By Lemma 12 the distinguished neighbors of v belong to C(v). If the polygon P representing C(v) in $\varGamma$ is convex, then each distinguished neighbor of v sees P, and hence the open straight-line segments connecting v with the vertices of C(v) lie in the interior of the polygon representing $c_G(v)$ in $\varGamma$. Again by Lemma 12, the vertices of $c_G(v)$ that are not in C(v) are adjacent to the distinguished neighbors of v, each of which hence sees the polygon representing $c_G(v)$ in $\varGamma$. Then we can just define $\varGamma ':=\varGamma$; note that no morph is actually needed in order to obtain the desired drawing $\varGamma '$ from $\varGamma$.

If P is not convex, then we show how an upward planar morph can be exploited to transform $\varGamma$ into an upward planar drawing $\varGamma '$ in which the polygon representing C(v) is convex, thus bringing us back to the previous case. Let $G^\circ$ be the subgraph of G obtained by removing all the vertices and edges in the interior of C(v) and let $\varGamma ^\circ$ be $\varGamma [G^\circ ]$. Observe that only v and its incident edges might be removed from G in order to obtain $G^\circ$.

We prove that $G^\circ$ is 3-connected. Suppose, for a contradiction, that $G^\circ$ contains a 2-cut $\{a,b\}$. If v was removed from G in order to obtain $G^\circ$, then $\{a,b,v\}$ is a 3-cut of G. Since G is maximal, any 3-cut induces a separating triangle, i.e., a 3-cycle with vertices both on the inside and on the outside. However, since v is simple, it is not part of any separating triangle, a contradiction. Assume next that v was not removed from G in order to obtain $G^\circ$. If $v \in \{a,b\}$, then $\{a,b\}$ is also a 2-cut of G, contradicting the fact that G is maximal (and hence 3-connected). Finally, if $v \notin \{a,b\}$, then $\{a,b,v\}$ is a 3-cut of G, and a contradiction can be derived as in the case in which v was removed from G.

Since $G^\circ$ is 3-connected and C(v) is an st-cycle (by Lemma 12), we can apply Lemma 9 to construct an upward planar drawing $\varGamma ^\diamondsuit$ of $G^\circ$ such that C(v) is strictly convex in $\varGamma ^\diamondsuit$ and $\langle \varGamma , \varGamma ^\diamondsuit \rangle$ is an upward planar morph.

We obtain our desired upward planar drawing $\varGamma '$ of G from $\varGamma ^\diamondsuit$ as follows.

If $G^\circ$ contains v, then we simply augment $\varGamma ^\diamondsuit$ by drawing the edges that are in G but not in $G^\circ$ as straight-line segments, thus obtaining $\varGamma '$. The convexity of C(v) in $\varGamma ^\diamondsuit$ implies that no crossings are introduced because of this augmentation. Further, as in the proof of Lemma 9, we have that $\varGamma$ and $\varGamma '$ have the same y-assignment, hence by Lemma 2 they are left-to-right equivalent, and thus by Lemma 4 the linear morph $\langle \varGamma , \varGamma ' \rangle$ is upward planar.

If $G^\circ$ does not contain v, then we need to determine a placement for v in $\varGamma ^\diamondsuit$ in order to obtain $\varGamma '$. We insert v in the interior of the convex polygon representing C(v) in $\varGamma ^\diamondsuit$, so that its y-coordinate is the same as in $\varGamma$. We draw the edges incident to v as straight-line segments. This ensures that $\varGamma$ and $\varGamma '$ have the same y-assignment and hence, as in the previous case, that the linear morph between them is upward planar. $\square$

The following concludes our discussion on maximal plane st-graph.

Theorem 4

Let $\varGamma _0$and $\varGamma _1$be two upward planar straight-line drawings of an n-vertex maximal plane st-graph G. There exists an O(n)-step upward planar morph from $\varGamma _0$to $\varGamma _1$.

Proof

The proof is by induction on n. In the base case we have $n=3$, hence $\varGamma _0$ and $\varGamma _1$ are two triangles. We show that $\varGamma _0$ and $\varGamma _1$ form an hvh-pair. Denote by u and w the source and the sink of G, respectively. Observe that the third vertex of G, call it v, is on the same side of the edge uw in $\varGamma _0$ and in $\varGamma _1$, as $\varGamma _0$ and in $\varGamma _1$ have the same upward planar embedding; assume that v lies to the right of uw, the other case is symmetric. For $i=0,1,$ let $\varGamma '_i$ be a drawing of G such that the x-coordinate of u and w is 0, the x-coordinate of v is 1, and y-coordinate of each vertex is the same as in $\varGamma _i$. It is easy to see that $\varGamma '_0$ and $\varGamma '_1$ are upward planar drawings of G and that these drawings, together with $\varGamma _0$ and $\varGamma _1$, satisfy Conditions (1)–(3) of the definition of an hvh-pair. Thus, by Lemma 5, there exists a 3-step upward planar morph from $\varGamma _0$ to $\varGamma _1$.

Suppose next that $n > 3$. By Lemma 10, G contains a simple vertex v of degree at most 5. By Lemma 11, v has at least one distinguished neighbor, which we denote by u. Assume for the remainder of the proof that u is a predecessor of v, the case in which it is a successor of v being symmetric. By Lemma 13, there exists an upward planar morph from $\varGamma _0$ to an upward planar drawing $\varGamma ^v_0$ in which u sees the polygon representing $c_G(v)$. Analogously, there exists an upward planar morph from $\varGamma _1$ to an upward planar drawing $\varGamma ^v_1$ in which u sees the polygon representing $c_G(v)$.

In order to obtain the morph from $\varGamma ^v_0$ to $\varGamma ^v_1$ we are going to apply induction. For this sake, we define an $(n-1)$-vertex maximal plane st-graph $G'$, and two upward planar drawings $\varGamma _0'$ and $\varGamma _1'$ of it. The graph $G'$ is obtained from G by removing v and by inserting a directed edge uq for each successor q of v that is not adjacent to u in G. These edges are all added inside $c_G(v)$. Note that, by the definition of distinguished predecessor, either u is the only predecessor of v, or v has one predecessor p different from u, where G contains the directed edge pu. The drawings $\varGamma _0'$ and $\varGamma _1'$ are obtained from $\varGamma ^v_0$ and $\varGamma ^v_1$, respectively, by removing v and its incident edges and by drawing the edges of $G'$ not in G as straight-line segments.

For $i=0,1$, since u sees the polygon representing $c_G(v)$ in $\varGamma ^v_i$, we have that $\varGamma '_i$ is planar. We prove that $\varGamma _i'$ is upward. Every successor q of v has a y-coordinate larger than the one of v in $\varGamma ^V_i$; since u has a y-coordinate smaller than the one of v in $\varGamma ^v_i$, it follows that the edge from u to q is monotonically increasing in the y-direction in $\varGamma '_i$. Since all the edges of $G'$ that are also in G are drawn as in $\varGamma ^v_i$ and since $\varGamma ^v_i$ is an upward drawing, it follows that $\varGamma '_i$ is an upward planar drawing of $G'$. Observe that $G'$ is an st-graph; indeed, it suffices to note that the edges that are removed from G do not result in any new source or sink in $G'$: (1) no successor q of v becomes a source in $G'$, as a directed edge uq is inserted in $G'$ if it is not in G; (2) no predecessor p of v different from u, if any, becomes a sink in $G'$, as the directed edge pu belongs to G; and (3) u does not become a sink in $G'$ as v has at least one successor in G. Finally, note that $G'$ is maximal, since G is maximal and the edges added to $G'$ triangulate the interior of $c_G(v)$. It follows that $G'$ is a maximal plane st-graph.

By induction, there exists an upward planar morph $\mathcal{M}'=\langle \varGamma '_0 = \varLambda _0, \varLambda _1, \dots , \varLambda _k=\varGamma '_1\rangle$ from $\varGamma '_0$ to $\varGamma '_1$, for some positive integer k. In the following we transform $\mathcal{M}'$ into an upward planar morph ${\mathcal{M}}$ between two new upward planar drawings $\varDelta _0$ and $\varDelta _k$ of G; such drawings coincide with $\varGamma ^v_0$ and $\varGamma ^v_1$, respectively, when restricted to the vertices and edges of $G - v$. This will be done by inserting v at a suitable point in the drawing of $G'$ at any time instant of the morph ${\mathcal{M}}'$ and by drawing the edges incident to v as straight-line segments. We will later show that ${\mathcal{M}}$ is actually composed of k linear morphs.²

Let $\varepsilon >0$ be a sufficiently small value such that the following properties are satisfied throughout ${\mathcal{M}}'$:

• (a) for each successor q of v in G, it holds true that $y(q) > y(u) + \varepsilon$;

• (b) if v has a predecessor $p\ne u$ in G, then $y(p) < y(u) - \varepsilon$; and

• (c) for any segment s of $c_G(v)$ not incident to u, the line through s does not intersect the disk $\delta$ with radius $\varepsilon$ centered at u.

Since ${\mathcal{M}}'$ is an upward planar morph and since $G'$ contains edges from u to every successor q of v and from every predecessor p of v to u, it follows that such a value $\varepsilon$ exists; in particular, standard continuity arguments, like the ones used in the proof of Fáry’s Theorem [21], ensure that Property (c) is satisfied for a sufficiently small value $\varepsilon >0$.

We distinguish the cases in which v has degree 3 or greater than 3 in G.

If v has degree 3 in G, then let a, b, and c be the neighbors of v in G, where $a=u$. We choose three values $\alpha , \beta$, and $\gamma$, as discussed below, and then place v at the point $\alpha \cdot a + \beta \cdot b + \gamma \cdot c$ at any time instant of ${\mathcal{M}}'$ (a, b, and c here represent the points at which the corresponding vertices are placed at any time instant of ${\mathcal{M}}'$). We choose $\alpha , \beta$, and $\gamma$ as any positive values such that $\alpha + \beta + \gamma = 1$ and such that the point $\alpha \cdot a + \beta \cdot b + \gamma \cdot c$ lies in $\delta$ throughout ${\mathcal{M}}'$. Note that v lies inside the triangle $c_G(v)$ for any positive values of $\alpha , \beta$, and $\gamma$ such that $\alpha + \beta + \gamma = 1$ (indeed, the position of v is a convex combination of the ones of a, b, and c); further, choosing $\alpha$ sufficiently close to 1 ensures that v is at distance at most $\varepsilon$ from u, and hence lies inside $\delta$, throughout ${\mathcal{M}}'$.

Suppose now that v has degree 4 or 5 in G. Since u is a distinguished predecessor of v, we have that v has at most two predecessors in G, one of which is u. If v has no predecessor other than u, then v has at least three successors in G; let w be a successor of v not adjacent to u in G. If v has a predecessor p different from u, then v has at least two successors in G; let w be the one adjacent to p in G. Note that, in both cases, the directed edge uw belongs to $G'$ but not to G and connects u with a successor w of v. We compute a value $\lambda$, as discussed below, and then place v at the point $\lambda \cdot u + (1-\lambda ) \cdot w$ at any time instant of ${\mathcal{M}}'$ (u and w here represent the points at which the corresponding vertices are placed at any time instant of $\mathcal{M}'$). We choose $\lambda$ as any positive value smaller than 1 such that the point $\lambda \cdot u + (1-\lambda ) \cdot w$ lies in $\delta$ throughout ${\mathcal{M}}'$. Note that v is on the straight-line segment representing the edge uw for any positive value of $\lambda$ smaller than 1 (indeed, the position of v is a convex combination of the ones of u and w); further, choosing $\lambda$ sufficiently close to 1 ensures that v is at distance at most $\varepsilon$ from u, and hence lies inside $\delta$, throughout ${\mathcal{M}}'$.

In both cases, the choice of $\varepsilon$ ensures that at any time instant of ${\mathcal{M}}$ the drawing of G is upward planar. In particular, Properties (a) and (b), together with the fact that every drawing of $G'$ in ${\mathcal{M}}'$ is upward, directly ensure that every drawing of G in ${\mathcal{M}}$ is upward. Further, Property (c), together with the fact that every drawing of $G'$ in ${\mathcal{M}}'$ is planar, ensures that every drawing of G in ${\mathcal{M}}$ is planar. In particular, the open straight-line segment between any point of $\delta$ and any vertex of $c_G(v)$ not adjacent to u lies in the interior of the polygon representing $c_G(v)$; hence the directed edges from v to its successors cause no crossings throughout ${\mathcal{M}}$. Further, if v has a predecessor p different from u, the fact that v lies on the straight-line segment connecting u with the neighbor of p in G ensures that the open straight-line segment between p and v lies in the interior of the polygon representing $c_G(v)$ throughout ${\mathcal{M}}$.

We now prove that ${\mathcal{M}}$ consists of k morphing steps. Assume that the degree of v is 3, the discussion for the case in which the degree of v is 4 or 5 being analogous and simpler. Denote by $\varDelta _i$ the drawing of G obtained from $\varLambda _i$ by placing v at the point $\alpha \cdot a_i + \beta \cdot b_i + \gamma \cdot c_i$, as discussed above, where by $a_i$, $b_i$, and $c_i$ denote the positions of the vertices a, b, and c in $\varLambda _i$, respectively. Hence, at any time $t\in [0;1]$ of the linear morph $\langle \varDelta _i,\varDelta _{i+1}\rangle$, the position of v is

$$\begin{aligned}&(1-t)\cdot (\alpha \cdot a_i + \beta \cdot b_i + \gamma \cdot c_i) + t\cdot (\alpha \cdot a_{i+1} + \beta \cdot b_{i+1} + \gamma \cdot c_{i+1})\\&\quad = \alpha ((1-t)\cdot a_i + t \cdot a_{i+1})+ \beta ((1-t)\cdot b_i + t \cdot b_{i+1})+ \gamma ((1-t)\cdot c_i + t \cdot c_{i+1}). \end{aligned}$$

Hence, the position of v at any time instant of the linear morph $\langle \varDelta _i,\varDelta _{i+1}\rangle$ is given by the convex combination with coefficients $\alpha$, $\beta$, and $\gamma$ of the positions of a, b, and c. It follows that the upward planar morph ${\mathcal{M}}$ defined above coincides with the k-step morph $\langle \varDelta _0, \varDelta _1, \dots , \varDelta _k\rangle$.

Figure 10 provides a schema for our algorithm.

Fig. 10

A description of the algorithm for morphing two upward planar straight-line drawings of the n-vertex maximal plane st-graph G when $n>3$. Each filled arrow represents a single morphing step, while each empty arrow represents the transformation of a drawing of one graph into a drawing of another graph

Finally, denote by f(n) the number of morphing steps of the described algorithm. We have $f(3)=3$ and $f(n)=4+f(n-1)$, if $n>3$. Indeed, in the inductive case the upward planar morph from $\varGamma _0$ to $\varGamma _1$ consists of:

• a first morphing step from the given drawing $\varGamma _0$ to the drawing $\varGamma ^v_0$ in which u sees the polygon representing $c_G(v)$;

• a second morphing step $\langle \varGamma ^v_0,\varDelta _0\rangle$ (note that only v moves during this morphing step);

• the morph ${\mathcal{M}}=\langle \varDelta _0, \varDelta _1, \dots , \varDelta _k\rangle$, whose number k of steps is the same as in ${\mathcal{M}}'$, which is the inductively constructed morph of the $(n-1)$-vertex maximal plane st-graph $G'$; hence $k=f(n-1)$;

• a second to last morphing step $\langle \varDelta _k,\varGamma ^v_1\rangle$, where in $\varGamma ^v_1$ the vertex u sees the polygon representing $c_G(v)$ (note that only v moves during this morphing step); and

• a final morphing step from the drawing $\varGamma ^v_1$ to the given drawing $\varGamma _1$.

The recurrence equation for f(n) solves to $f(n)=4n-9$. This concludes the proof of the theorem. $\square$

We finally get the following.

Corollary 1

Let $\varGamma _0$and $\varGamma _1$be two upward planar drawings of an n-vertex plane st-graph. There exists an O(n)-step upward planar morph from $\varGamma _0$to $\varGamma _1$.

Proof

The statement follows by Lemma 8 and Theorem 4. $\square$

5 Upward Plane Graphs

In this section we deal with general upward plane graphs. In order to morph two upward planar drawings of an upward plane graph G we are going to augment the upward planar drawings of G to two upward planar drawings of a (possibly reduced) plane st-graph $G'$ and then to use the results of Sect. 4 for morphing the obtained upward planar drawings of $G'$. The augmentation process itself uses upward planar morphs. In the following we formally describe this strategy.

Let G be an upward plane graph whose underlying graph is biconnected, let f be a face of G which is not an st-face, and let u, v, and w be three clockwise consecutive switches of f. Further, let $v^-$ and $v^+$ be the vertices preceding and succeeding v in clockwise order along the boundary of f, respectively, and let $u^-$ and $u^+$ be the vertices preceding and succeeding u in clockwise order along the boundary of f, respectively. We say that [u, v, w] is a pocket for f if $\angle (v^-,v,v^+)= \texttt {small}$ and $\angle (u^-,u,u^+) = \texttt {large}$. The following is well-known.

Lemma 14

(Bertolazzi et al. [10]) Let G be an upward plane graph whose underlying graph is biconnected and let f be a face of G that is not an st-face. Then, there exists a pocket [u, v, w] for f.

Next, we give a lemma that shows how to “simplify” a face of an upward plane graph that is not an st-graph, by removing one of its pockets.

Lemma 15

Let G be an n-vertex (reduced) upward plane graph whose underlying graph is biconnected, let f be a face of G that is not an st-face, let [u, v, w] be a pocket for f, and let $\varGamma$be an upward planar drawing of G.

Suppose that an algorithm ${\mathcal{A}}$ (${\mathcal{A}}_R$) exists that constructs an f(r)-step ($f_R(r)$-step) upward planar morph between any two upward planar drawings of an r-vertex (reduced) plane st-graph.

Then, there exists an O(f(n))-step (an $O(f_R(n))$-step) upward planar morph from $\varGamma$to an upward planar drawing $\varGamma ^*$of G in which the open straight-line segment between u and w lies inside f and in which u lies below w, if the directed path between u and v along the boundary of f is directed from v to u, or u lies above w, otherwise.

Proof

Suppose that the directed path $p_{vu}$ between u and v along the boundary of f is directed from v to u (refer to Fig. 11a); the case in which it is directed from u to v can be treated symmetrically.

Fig. 11

Illustrations for the proof of Lemma 15. a The upward planar drawing $\varGamma$ of G; in particular, the illustration shows the face f whose boundary contains the pocket [u, v, w]. b The upward planar drawing $\varGamma '$ of G (plus the directed paths $p'$ and $p''$). c The upward planar drawing $\varGamma ^*$ of G (plus the directed edge uw)

The proof is structured as follows. First, we show that there exists an upward planar drawing $\varGamma '$ of G such that (see Fig. 11b):

• 1. the upward planar drawings of two directed paths $p'$ and $p''$ from u to w can be inserted in $\varGamma '$ in the interior of f; and

• 2. there exists an O(f(n))-step (an $O(f_R(n))$-step) upward planar morph ${\mathcal{M}}'$ from $\varGamma$ to $\varGamma '$.

Second, we show that there exists an upward planar drawing $\varGamma ^*$ of G such that (see Fig. 11c):

• 3. the open straight-line segment between u and w lies inside f and u lies below w, and

• 4. there exists an O(f(n))-step (an $O(f_R(n))$-step) upward planar morph ${\mathcal{M}}^*$ from $\varGamma '$ to $\varGamma ^*$.

The lemma follows from the existence of the drawings $\varGamma '$ and $\varGamma ^*$ above, since composing ${\mathcal{M}}'$ with ${\mathcal{M}}^*$ yields the desired upward planar morph with O(f(n)) steps (with $O(f_R(n))$ steps).

Fig. 12

Construction of the drawing $\varGamma '$; only what happens to the face f is shown. The drawing $\varGamma _1$ of $G_1$. The face g is gray

The drawing $\varGamma '$ is constructed in four phases.

In phase 1 we augment $\varGamma$ to an upward planar drawing $\varGamma _1$ of an upward plane graph $G_1$. The goal of this phase is to insert in the drawing the part of the path $p'$ from a vertex $v'$ to w and the part of the path $p''$ from a vertex $v''$ to w; moreover, an st-face g incident to $v'$, $v''$, and u is also created. Refer to Fig. 12. Let $p_{vu}=v u_1 \dots u_k u$ and $p_{vw}=v w_1 \dots w_h w$ be the directed paths from v to u and from v to w, respectively, that belong to the boundary of f. In order to construct $\varGamma _1$ and $G_1$ we insert, for some sufficiently small $\epsilon >0$, the following directed paths inside f into $\varGamma$ and G:

• (a) a directed path $q_1=v v'w'_1\dots w'_h w$, where $w'_i$ is on the same horizontal line as $w_i$, at horizontal distance $\epsilon /2$ from it, while $v'$ is above v, at distance $\epsilon /2$ from it, along the bisector of the angle $\angle (v^-,v,v^+)$;

• (b) a directed path $q_2=v' v''w''_1\dots w''_h w$, where $w''_i$ is on the same horizontal line as $w_i$, at horizontal distance $\epsilon$ from it, while $v''$ is above v and $v'$, at distance $\epsilon$ from v, along the bisector of the angle $\angle (v^-,v,v^+)$;

• (c) a directed path $q_3=v''u'_1\dots u'_k u'$, where $u'_i$ is on the same horizontal line as $u_i$, at horizontal distance $\epsilon$ from it, while $u'$ is above u, at distance $\epsilon$ from it, along the bisector of the angle $\angle (u^-,u,u^+)$; and

• (d) a directed edge $uu'$.

It is easy to see that the resulting drawing $\varGamma _1$ has no crossings and that the directed paths $q_1$, $q_2$, $q_3$, and $uu'$ are upwardly drawn inside f, provided that $\epsilon$ is small enough. Note that there is an st-face g of $G_1$ that is delimited by the directed path composed of $vv'v''$ and of $q_3$ and by the directed path composed of $p_{vu}$ and of $uu'$.

Fig. 13

Construction of the drawing $\varGamma '$; only what happens to the face f is shown. The drawing $\varGamma _2$ of $G_2$

In phase 2 we augment $\varGamma _1$ to an upward planar drawing $\varGamma _2$ of a plane st-graph $G_2$. The goal of this phase is to triangulate every face of $G_1$ different from g. Refer to Fig. 13. In order to construct $\varGamma _2$, we insert edges drawn as straight-line segments into every face of $\varGamma _1$, except for g, until no further edge can be inserted while maintaining planarity; each inserted edge is oriented from the endpoint with the lowest y-coordinate to the endpoint with the highest y-coordinate in $\varGamma _1$ (if the end-points of an edge have the same y-coordinate, then we insert two new adjacent vertices, slightly above and below the middle point of that edge, and then keep on inserting edges). This concludes the construction of the drawing $\varGamma _2$ of $G_2$. Since $\varGamma _1$ is upward and planar, it follows that $\varGamma _2$ is upward and planar as well. Further, $G_2$ is an st-graph by Lemma 1, since g is an st-face, as argued above, and since all the faces of $G_2$ different from g are also delimited by st-cycles, as otherwise more edges could have been introduced while maintaining the planarity of $\varGamma _2$; note that every internal face of $\varGamma _2$ different from g is delimited by an upwardly drawn 3-cycle, while more than 3 vertices might be incident to the outer face of $\varGamma _2$.

In phase 3 we replace each directed edge uv of $G_2$ that does not belong to G (and has been inserted in phase 1 or 2) with a directed path $(u,w_{uv},v)$ and insert $w_{uv}$ at an arbitrary internal point of the edge uv in $\varGamma _2$. Clearly, the resulting graph $G_3$ is a plane st-graph and it is reduced if G is. Further, the resulting drawing $\varGamma _3$ is an upward planar drawing of $G_3$.

Fig. 14

Construction of the drawing $\varGamma '$; only what happens to the face f is shown. The drawing $\varGamma _4$ of $G_4$; the paths $p'$ and $p''$ are thick and red (Color figure online)

In phase 4 we augment $G_3$ to a plane st-graph $G_4$ by adding two directed edges $uv'$ and $uv''$ inside g; this completes the insertion of the paths $p'$ and $p''$ into the graph. Observe that $G_4$ is a plane st-graph, by Lemma 1, since the directed edges $uv'$ and $uv''$ split g into three st-faces. Further, $G_4$ is reduced if G is. Let $p'$ be the directed path composed of $uv'$ and of the (subdivided) directed path $q_1$ and let $p''$ be the directed path composed of $uv'$ and of the (subdivided) directed path $q_2$. Observe that the st-cycle ${\mathcal{D}}$ of $G_4$ composed of $p'$ and $p''$ does not enclose any vertex of G, although it encloses vertices of $G_4$ not in G. We construct an upward planar straight-line drawing $\varGamma _4$ of $G_4$ by means of, e.g., the algorithm by Di Battista and Tamassia [19]. Refer to Fig. 14.

Now let $\varGamma ' = \varGamma _4[G]$. Property (1) then follows from the fact that upward planar drawings of the directed paths $p'$ and $p''$ from u to w can be inserted in $\varGamma '$ as they are drawn in $\varGamma _4$. Further, since $G_3$ has O(n) vertices, by applying algorithm ${\mathcal{A}}$ (${\mathcal{A}}_R$) we can construct an O(f(n))-step (an $O(f_R(n))$-step) upward planar morph $\mathcal{M}_{3,4}$ from $\varGamma _3$ to $\varGamma _4[G_3]$. Since $\varGamma =\varGamma _3[G]$ and $\varGamma ' = \varGamma _4[G]$, the restriction of ${\mathcal{M}}_{3,4}$ to the vertices and edges of G provides an O(f(n))-step (an $O(f_R(n))$-step) upward planar morph $\mathcal{M}'$ from $\varGamma$ to $\varGamma '$, which proves Property (2).

The drawing $\varGamma ^*$ is constructed as follows.

First, we remove from $\varGamma _4$ and $G_4$ all the vertices and edges enclosed by ${\mathcal{D}}$. Let $\varGamma _5$ and $G_5$ be the resulting drawing and the resulting graph, respectively. We have that $G_5$ is a plane st-graph by Lemma 1; indeed, the face d of $G_5$ delimited by ${\mathcal{D}}$ is an st-face, as ${\mathcal{D}}$ is composed of the directed paths $p'$ and $p''$, and every other face of $G_5$ is an st-face since it is also a face of $G_4$, which is a plane st-graph. Moreover, $\varGamma _5$ is an upward planar drawing of $G_5$, given that $\varGamma _4$ is an upward planar drawing of $G_4$.

Second, we augment $G_5$ to a plane st-graph $G_6$ by inserting the directed edge uw inside d. We construct an upward planar straight-line drawing $\varGamma _6$ of $G_6$ by means of, e.g., the algorithm by Di Battista and Tamassia [19].

Now let $\varGamma ^* = \varGamma _6[G]$. Property (3) then follows from the fact that the directed edge uw lies inside f and is upwardly drawn in $\varGamma _6$. Further, since $G_6$ has O(n) vertices, by applying algorithm ${\mathcal{A}}$ (${\mathcal{A}}_R$) we can construct an O(f(n))-step (an $O(f_R(n))$-step) upward planar morph $\mathcal{M}_{5,6}$ from $\varGamma _5$ to $\varGamma _6[G_5]$. Since $\varGamma '=\varGamma _5[G]$ and $\varGamma ^* = \varGamma _6[G]$, the restriction of ${\mathcal{M}}_{5,6}$ to the vertices and edges of G provides an O(f(n))-step (an $O(f_R(n))$-step) upward planar morph $\mathcal{M}^*$ from $\varGamma '$ to $\varGamma ^*$, which proves Property (4). This concludes the proof of the lemma. $\square$

We are now ready to prove the following.

Theorem 5

Let $\varGamma _0$and $\varGamma _1$be two upward planar straight-line drawings of an n-vertex (reduced) upward plane graph G.

Suppose that an algorithm ${\mathcal{A}}$ (${\mathcal{A}}_R$) exists that constructs an f(r)-step (an $f_R(r)$-step) upward planar morph between any two upward planar straight-line drawings of an r-vertex (reduced) plane st-graph.

There exists an $O(n\cdot f(n))$-step (an $O(n \cdot f_R(n))$-step) upward planar morph from $\varGamma _0$to $\varGamma _1$.

Proof

By Lemma 6, we can assume that G is biconnected.

Denote by $\ell (G)$ the number of switches labeled large in the upward planar embedding of G. In order to prove the statement, we show that there exists a $((2\ell (G)-3) \cdot f(n))$-step (a $((2\ell (G)-3) \cdot f_R(n))$-step) upward planar morph from $\varGamma _0$ to $\varGamma _1$, if G is a (reduced) upward plane graph. Since $\ell (G) \in O(n)$, the statement follows. The proof is by induction on $\ell (G)$.

In the base case $\ell (G)=2$ and thus G is a (reduced) plane st-graph (the two switches labeled large are those incident to the outer face of G). Hence, by applying algorithm ${\mathcal{A}}$ (${\mathcal{A}}_R$) to $\varGamma _0$ and $\varGamma _1$, we obtain an f(n)-step (an $f_R(n)$-step) upward planar morph from $\varGamma _0$ to $\varGamma _1$.

In the inductive case $\ell (G)>2$. Then there exists a face f of G that is not an st-face. Thus, by Lemma 14, there exists a pocket [u, v, w] for f. By Lemma 15, we can construct upward planar drawings $\varGamma '_0$ and $\varGamma '_1$ of G in which the open straight-line segment between u and w lies inside f and in which u lies below w (assuming that a directed path exists in f from v to u, the other case being symmetric), and such that there exists an f(n)-step (an $f_R(n)$-step) upward planar morph ${\mathcal{M}}_{start}$ from $\varGamma _0$ to $\varGamma '_0$ and an f(n)-step (an $f_R(n)$-step) upward planar morph $\mathcal{M}_{finish}$ from $\varGamma '_1$ to $\varGamma _1$.

Let $G^*$ be the plane graph obtained from G by splitting f with a directed edge uw. The graph $G^*$ is an upward plane graph whose upward planar embedding is constructed by assigning to each switch in $G^*$ the same label small or large it has in G. Then $\ell (G^*) = \ell (G)-1$, since u is not a switch in $G^*$. Further, $G^*$ is reduced if G is reduced, since there exists no directed path in G passing first through u and then through w, given that u is a sink of G.

Let $\varGamma ^*_0$ and $\varGamma ^*_1$ be the upward planar straight-line drawings of $G^*$ obtained by drawing the directed edge uw as a straight-line segment connecting u and w in $\varGamma '_0$ and in $\varGamma '_1$, respectively. By the inductive hypothesis and since $V(G^*)=V(G)$, we can construct a $((2\ell (G^*)-3)\cdot f(n))$-step (a $((2\ell (G^*)-3)\cdot f_R(n))$-step) upward planar morph from $\varGamma ^*_0$ to $\varGamma ^*_1$. Observe that, since $G \subset G^*$, restricting each drawing in ${\mathcal{M}}^*$ to the vertices and edges of G yields a $\big ( (2\ell (G)-5)\cdot f(n) \big )$-step upward planar morph ${\mathcal{M}}^-$ of G from $\varGamma '_0$ to $\varGamma '_1$. Therefore, by concatenating morphs ${\mathcal{M}}_{start}$, $\mathcal{M}^-$, and ${\mathcal{M}}_{finish}$, we obtain a $\big ( (2\ell (G)-3) \cdot f(n) \big )$-step (a $\big ( (2\ell (G)-3) \cdot f_R(n) \big )$-step) upward planar morph of G from $\varGamma _0$ to $\varGamma _1$. This concludes the proof. $\square$

Theorem 2, Corollary 1, and Theorem 5 imply the following main result.

Theorem 6

Let $\varGamma _0$and $\varGamma _1$be two upward planar straight-line drawings of the same n-vertex (reduced) upward plane graph. There exists an $O(n^2)$-step (an O(n)-step) upward planar morph from $\varGamma _0$to $\varGamma _1$.

6 Conclusions and Open Problems

In this paper, we addressed for the first time the problem of morphing upward planar straight-line drawings. We proved that an upward planar morph between any two upward planar straight-line drawings of the same upward plane graph always exists; such a morph consists of a quadratic number of linear morphing steps. The quadratic bound can be improved to linear for reduced upward plane graphs and for plane st-graphs, and to constant for reduced plane st-graphs. It is straight-forward to implement our algorithms so that they run in polynomial time in the real RAM model of computation, in which arithmetic operations on the reals can be carried out in constant time.

Our algorithms assume the (undirected) connectivity of the upward planar graph whose drawings have to be morphed. However, we believe that the techniques presented in [2] in order to deal with disconnected graphs can be applied also to our setting with only minor modifications.

Several problems are left open by our research. In our opinion the most interesting question is whether an O(1)-step upward planar morph between any two upward planar drawings of the same maximal plane st-graph exists; note that no o(n) bound is indeed known. In case of a positive answer, by Lemma 8 and Theorem 5, an optimal O(n)-step upward planar morph would exist between any two upward planar drawings of the same n-vertex upward plane graph. In case of a negative answer, it would be interesting to find broad classes of upward plane graphs that admit upward planar morphs with a sub-linear number of steps. In particular, we ask whether series-parallel digraphs [9, 15] admit upward planar morphs with O(1) steps. Moreover, for visualization purposes, it would be interesting to study upward planar morphs with polynomially-bounded resolution. For instance, Barrera-Cruz et al. [7] presented an algorithm for constructing morphs with a linear number of steps between any two upward planar grid drawings $\varGamma _0$ and $\varGamma _1$ of n-vertex rooted trees, in which each intermediate grid drawing has linear width and height, where the input size is measured by n and by the width and the height of $\varGamma _0$ and $\varGamma _1$.