How to Morph a Tree on a Small Grid

Abstract

In this paper we study planar morphs between straight-line planar grid drawings of trees. A morph consists of a sequence of morphing steps, where in a morphing step vertices move along straight-line trajectories at constant speed. We show how to construct planar morphs that simultaneously achieve a reduced number of morphing steps and a polynomially-bounded resolution. We assume that both the initial and final drawings lie on the grid and we ensure that each morphing step produces a grid drawing; further, we consider both upward drawings of rooted trees and drawings of arbitrary trees.

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 problem of morphing combinatorial structures is a consolidated research topic with important applications in several areas of Computer Science such as Computational Geometry, Computer Graphics, Modeling, and Animation. The structures of interest typically are drawings of graphs; a between two drawings $\varGamma _0$ and $\varGamma _{1}$ of the same graph G is defined as a continuously changing family of drawings $\{\varGamma _{t}\}$ 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$. A morph is usually required to preserve a certain drawing standard and pursues certain qualities.

The is the set of the geometric properties that are maintained at any time during the morph. For example, if both $\varGamma _{0}$ and $\varGamma _{1}$ are planar drawings, then the drawing standard might require that all the drawings of the morph are planar. Other properties that might be required to be preserved are the convexity of the faces, or the fact that the edges are straight-line segments, etc.

Regarding the of the morph, the research up to now mainly focused on limiting the number of , where in a morphing step vertices move along straight-line trajectories at constant speed. A morph $\mathcal {M}$ can then be described as a sequence of drawings $\mathcal {M}=\langle \varGamma _0=\varDelta _0,\varDelta _1,\dots ,\varDelta _{k}=\varGamma _1\rangle$ where the morph $\langle \varDelta _{i-1}, \varDelta _{i} \rangle$, for $i=1, \dots , k$, is a morphing step. Following the pioneeristic works of Cairns and Thomassen [8, 13], most of the literature focused on the straight-line planar drawing standard. A sequence of recent results in [1,2,3,4,5] proved that a linear number of morphing steps suffices, and is sometimes necessary, to construct a morph between any two straight-line planar drawings of a graph.

Although the results mentioned in the previous paragraph establish strong theoretical foundations for the topic of morphing graph drawings, they produce morphs that are not appealing from a visualization perspective. Namely, such algorithms produce drawings that have poor , i.e., they may have an exponential ratio of the distances between the farthest and closest pairs of geometric objects (points representing vertices or segments representing edges), even if the same ratio is polynomially bounded in the initial and final drawings. Indeed, most of the above cited papers mention the problem of constructing morphs with bounded resolution as the main challenge in this research area.

The only paper we are aware of where the resolution problem has been successfully addressed is the one by Barrera-Cruz et al. [6], who showed how to construct a morph with polynomially-bounded resolution between two $\varGamma _0$ and $\varGamma _1$ of the same planar triangulation. The model they use in order to ensure a bound on the resolution requires that $\varGamma _0=\varDelta _0,\varDelta _1,\dots ,\varDelta _{k}=\varGamma _1$ are , i.e., vertices have integer coordinates, and the resolution is measured by comparing the area of $\varGamma _0$ and $\varGamma _1$ with the area of the $\varDelta _i$’s. We remark that morphs between planar orthogonal drawings of maximum-degree-4 planar graphs, like those in [7, 12], inherently have polynomial resolution.

In this paper we show how to construct morphs of tree drawings that simultaneously achieve a reduced number of morphing steps and a polynomially-bounded resolution. Adopting the setting of [6], we assume that $\varGamma _0$ and $\varGamma _1$ are grid drawings and we ensure that each morphing step produces a grid drawing.

We present three algorithms. The first two algorithms construct morphs between any two strictly-upward straight-line planar grid drawings $\varGamma _0$ and $\varGamma _1$ of n-node rooted trees; drawings are such that each node lies above its children. Both algorithms construct morphs 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$. The first algorithm employs $\varTheta (n)$ morphing steps. The second algorithm employs $\varTheta (1)$ morphing steps, however it only applies to binary trees. The third algorithm allows us to achieve our main result, namely that for any two straight-line planar grid drawings $\varGamma _0$ and $\varGamma _1$ of an n-node tree, there is a planar morph with $\varTheta (n)$ morphing steps between $\varGamma _0$ and $\varGamma _1$ such that each intermediate grid drawing has polynomial area, where the input size is again measured by n and by the width and the height of $\varGamma _0$ and $\varGamma _1$.

The first algorithm uses recursion; namely, it eliminates a leaf in the tree, it recursively morphs the drawings of the remaining tree and it then reintroduces the removed leaf in suitable positions during the morph. The second algorithm morphs the given drawings by independently changing their x- and y-coordinates; this technique is reminiscent of a recent paper by Da Lozzo et al. [10]. Finally, the third algorithm scales the given drawings up in order to make room for a bottom-up modification of each drawing into a “canonical” drawing of the tree.

Missing proofs can be found in the full version of the paper.

2 Preliminaries

In this section we introduce some definitions and preliminaries; see also [11].

Trees. The node and edge sets of a tree T are denoted by V(T) and E(T), respectively. The $\deg (v)$ of a node v of T is the number of its neighbors. In an tree, a counter-clockwise order of the edges incident to each node is specified.

A T is a tree with one distinguished node, which is called and is denoted by r(T). For any node $u \in V(T)$ with $u\ne r(T)$, the p(u) of u is the neighbor of u in the unique path from u to r(T). For any node $u\in V(T)$ with $u\ne r(T)$, the of u are the neighbors of u different from p(u); the of r(T) are all its neighbors. The nodes that have children are called ; a non-internal node is a . For any node $u\in V(T)$ with $u\ne r(T)$, the $T_u$ of T rooted at u is defined as follows: remove from T the edge (u, p(u)), thus separating T in two trees; the one containing u is the subtree of T rooted at u. If each node of T has at most two children, then T is a .

An is a tree that is rooted and ordered. In an ordered rooted tree T, for each node $u\in V(T)$, a (linear) order $u_1,\dots ,u_k$ of the children of u is specified. If T is binary then the first (second) child in the left-to-right order of the children of any node u is the left () of u, and the subtree rooted at the left (right) child of u is the () of u.

Tree Drawings. In a $\varGamma$ of a tree T each node u is represented by a point of the plane (whose coordinates are denoted by $x_{\varGamma }(u)$ and $y_{\varGamma }(u)$) and each edge is represented by a straight-line segment between its end-points. All the drawings considered in this paper are straight-line, even when not specified. In a drawing no two edges intersect except, possibly, at common end-points. For a rooted tree T, a drawing $\varGamma$ is such that each edge $(u,p(u))\in E(T)$ is represented by a curve monotonically increasing in the y-direction from u to p(u); if $\varGamma$ is a straight-line drawing, this is equivalent to requiring that $y_{\varGamma }(u)<y_{\varGamma }(p(u))$. For an ordered tree T, an drawing $\varGamma$ is such that, for each node $u\in V(T)$, the counter-clockwise order of the edges incident to u in $\varGamma$ is the same as the order associated with u in T.

The of a drawing $\varGamma$ is the smallest axis-parallel rectangle enclosing $\varGamma$. In a drawing $\varGamma$ each node has integer coordinates; then the and the of $\varGamma$, denoted by $w(\varGamma )$ and $h(\varGamma )$, respectively, are the number of grid columns and rows intersecting the bounding box of $\varGamma$, while the of $\varGamma$ is its width times its height. For a node v in a drawing $\varGamma$, an v is the convex hull of the square whose corners are $(x_\varGamma (v) \pm \frac{\ell }{2}, y_\varGamma (v) \pm \frac{\ell }{2})$.

Morphs. A morph is if all its intermediate drawings are planar. A morph between two strictly-upward drawings of a rooted tree is if all its intermediate drawings are strictly-upward. A morph is if each node moves along a straight-line trajectory at constant speed. Whenever the linear morph between two straight-line planar drawings $\varGamma _0$ and $\varGamma _1$ of a graph G is not planar, one is usually interested in the construction of a piecewise-linear morph with small complexity between $\varGamma _0$ and $\varGamma _1$. This is formalized by defining a between $\varGamma _0$ and $\varGamma _1$ as a sequence $\langle \varGamma _0=\varDelta _0,\varDelta _1,\dots ,\varDelta _k=\varGamma _1 \rangle$ of drawings of G such that the linear morph $\langle \varDelta _{i-1},\varDelta _{i} \rangle$ is planar, for $i=1,\dots ,k$; each linear morph $\langle \varDelta _{i-1},\varDelta _{i} \rangle$ is called a or simply a .

The $w(\mathcal M)$ of a morph $\mathcal M=\langle \varDelta _0,\varDelta _1,\dots ,\varDelta _k \rangle$, where $\varDelta _i$ is a grid drawing, for $i=0,1,\dots ,k$, is equal to $\max \{w(\varDelta _0),w(\varDelta _1),\dots ,w(\varDelta _k)\}$. The $h(\mathcal M)$ of $\mathcal M$ is defined analogously. The of a morph $\mathcal M$ is defined as $w(\mathcal M)\times h(\mathcal M)$.

The algorithms we design in this paper receive in input two order-preserving straight-line planar grid drawings $\varGamma _0$ and $\varGamma _1$ of an ordered tree and construct morphs $\langle \varGamma _0=\varDelta _0,\varDelta _1,\dots ,\varDelta _k=\varGamma _1 \rangle$ with few steps and small area.

Remark 1

A necessary and sufficient condition for the existence of a planar morph between two straight-line planar drawings $\varGamma _0$ and $\varGamma _1$ of a tree T is that they are “topologically-equivalent”, i.e., the counter-clockwise order of the edges incident to each node $u\in V(T)$ is the same in $\varGamma _0$ and $\varGamma _1$. In order to better exploit standard terminology about tree drawings, we ensure that $\varGamma _0$ and $\varGamma _1$ are topologically-equivalent by assuming that T is ordered and that $\varGamma _0$ and $\varGamma _1$ are order-preserving drawings; hence, dealing with ordered trees and with order-preserving drawings is not a loss of generality.

Remark 2

The width and height of the morphs we construct are expressed not only in terms of the number of nodes of the input tree T, but also in terms of the width and height of the input drawings $\varGamma _0$ and $\varGamma _1$ of T; this is necessary, given that $\max \{w(\varGamma _0),w(\varGamma _1)\}$ and $\max \{h(\varGamma _0),h(\varGamma _1)\}$ are obvious lower bounds for the width and height of any morph between $\varGamma _0$ and $\varGamma _1$, respectively.

Remark 3

The morphs $\langle \varDelta _0,\varDelta _1,\dots ,\varDelta _k \rangle$ we construct in this paper are such that $\varDelta _0,\varDelta _1,\dots ,\varDelta _k$ are drawings, even when not explicitly specified.

3 Upward Planar Morphs of Rooted-Tree Drawings

In this section we study small-area morphs between order-preserving strictly-upward straight-line planar grid drawings of rooted ordered trees.

Our first result shows that such morphs can always be constructed consisting of a linear number of steps. This is obtained via an inductive algorithm which is described in the following. Let T be an n-node rooted ordered tree. The of T is the maximal path $(s_0,\dots ,s_m)$ such that $s_0=r(T)$ and $s_{i}$ is the rightmost child of $s_{i-1}$, for $i=1,\dots ,m$. Note that $s_m$ is a leaf, which is called the $l^{\rightarrow }_T$ of T. For a straight-line grid drawing $\varGamma$, denote by $\ell _{\varGamma }$ the rightmost vertical line intersecting $\varGamma$; note that $\ell _{\varGamma }$ is a grid column.

Let $\varGamma _0$ and $\varGamma _1$ be two order-preserving strictly-upward straight-line planar grid drawings of T. We inductively construct a morph $\mathcal M$ from $\varGamma _0$ to $\varGamma _1$ as follows.

In the base case $n=1$; then $\mathcal M$ is the linear morph $\langle \varGamma _0,\varGamma _1\rangle$.

In the inductive case $n>1$. Let $l=l^{\rightarrow }_T$ be the rightmost leaf of T. Let $\pi =p(l)$ be the parent of l. Let $T'$ be the $(n-1)$-node tree obtained from T by removing the node l and the edge $(\pi ,l)$. Let $\varGamma '_0$ and $\varGamma '_1$ be the drawings of $T'$ obtained from $\varGamma _0$ and $\varGamma _1$, respectively, by removing the node l and the edge $(\pi ,l)$. Inductively compute a k-step upward planar morph $\mathcal M'=\langle \varGamma '_0=\varDelta '_1,\varDelta '_2,\dots ,\varDelta '_{k}=\varGamma '_1\rangle$.

Fig. 1.

The 3-step morph $\langle \varGamma _0,\varGamma '_0,\varGamma '_1,\varGamma _1 \rangle$.

We now construct a morph $\mathcal M=\langle \varGamma _0,\varDelta _1,\varDelta _2,\dots ,\varDelta _k,\varGamma _1\rangle$. For each $i=2,3,\dots ,k-1$, we define $\varDelta _i$ as the drawing obtained from $\varDelta '_i$ by placing l one unit below $\pi$ and one unit to the right of $\ell _{\varDelta '_i}$. Further, we define $\varDelta _1$ ($\varDelta _{k}$) as the drawing obtained from $\varDelta '_1$ (resp. from $\varDelta '_k$) by placing l one unit below $\pi$ and one unit to the right of $\ell _{\varGamma _0}$ (resp. $\ell _{\varGamma _1}$). Note that the point at which l is placed in $\varDelta _1$ (in $\varDelta _k$) is one unit to the right of $\ell _{\varDelta '_1}$ (resp. $\ell _{\varDelta '_k}$), similarly as in $\varDelta _2, \varDelta _3, \dots , \varDelta _{k-1}$, except if l is to the right of every other node of $\varGamma _0$ (of $\varGamma _1$); in that case l might be several units to the right of $\ell _{\varDelta '_1}$ (resp. $\ell _{\varDelta '_k}$). This completes the construction of $\mathcal M$. We get the following.

Theorem 1

Let T be an n-node rooted ordered tree, and let $\varGamma _0$ and $\varGamma _1$ be two order-preserving strictly-upward straight-line planar grid drawings of T. There exists a $(2n-1)$-step upward planar morph $\mathcal M$ from $\varGamma _0$ to $\varGamma _1$ with $h(\mathcal M) = \max \{h(\varGamma _0),h(\varGamma _1)\}$ and $w(\mathcal M) = \max \{w(\varGamma _0),w(\varGamma _1)\} +n-1$.

In view of 1, it is natural to ask whether a sub-linear number of steps suffices to construct a small-area morph between any two order-preserving strictly-upward straight-line planar grid drawings of a rooted ordered tree. In the following we prove that this is indeed the case for binary trees, for which just three morphing steps are sufficient.

Our algorithm borrows ideas from a recent paper by Da Lozzo et al. [10], which deals with upward planar morphs of .

Consider any two order-preserving strictly-upward straight-line planar grid drawings $\varGamma _0$ and $\varGamma _1$ of an n-node rooted ordered binary tree T. We define two order-preserving strictly-upward straight-line planar grid drawings $\varGamma '_0$ and $\varGamma '_1$ of T such that the 3-step morph $\langle \varGamma _0,\varGamma '_0,\varGamma '_1,\varGamma _1 \rangle$ is upward and planar.

For $i=0,1$, we define $\varGamma '_i$ recursively as follows; see 1. Let $x_{\varGamma '_i}(r(T))=0$ and let $y_{\varGamma '_i}(r(T))=y_{\varGamma _i}(r(T))$. If the left subtree L of r(T) is non-empty, then recursively construct a drawing of it. Let $x_M$ be the maximum x-coordinate of a node in the constructed drawing of L; horizontally translate such a drawing by subtracting $x_M+1$ from the x-coordinate of every node in L, so that the maximum x-coordinate of any node in L is now $-1$. Symmetrically, if the right subtree R of r(T) is non-empty, then recursively construct a drawing of it. Let $x_m$ be the minimum x-coordinate of a node in the constructed drawing of R; horizontally translate such a drawing by subtracting $x_m-1$ from the x-coordinate of every node in R, so that the minimum x-coordinate of any node in R is now 1.

Theorem 2

Let T be an n-node rooted ordered binary tree, and let $\varGamma _0$ and $\varGamma _1$ be two order-preserving strictly-upward straight-line planar grid drawings of T. There exists a 3-step upward planar morph $\mathcal M$ from $\varGamma _0$ to $\varGamma _1$ with $h(\mathcal M) = \max \{h(\varGamma _0),h(\varGamma _1)\}$ and $w(\mathcal M) = \max \{w(\varGamma _0),w(\varGamma _1),n\}$.

The algorithm presented before  2 can be easily generalized to rooted ordered trees with unbounded degree. Thus, there exists a 3-step upward planar morph between any two order-preserving strictly-upward straight-line planar grid drawings of an n-node rooted ordered tree. However, the generalized version of the algorithm does not guarantee polynomial bounds on the width of the morph.

Fig. 2.

Four canonical drawings of a tree T (each shown in a differently colored quadrant).

4 Planar Morphs of Tree Drawings

In this section we show how to construct small-area morphs between straight-line planar grid drawings of trees. In particular, we prove the following result.

Theorem 3

Let T be an n-node ordered tree and let $\varGamma _0$ and $\varGamma _1$ be two order-preserving straight-line planar grid drawings of T. There exists an O(n)-step planar morph $\mathcal M$ from $\varGamma _0$ to $\varGamma _1$ with $h(\mathcal M) \in O(D^3n \cdot H)$ and $w(\mathcal M) \in O(D^3 n \cdot W)$, where $H = \max \{h(\varGamma _0),h(\varGamma _1)\}$, $W = \max \{w(\varGamma _0),w(\varGamma _1)\}$, and $D = \max \{H,W\}$.

The rest of this section is devoted to the proof of 3. We are going to use the following definition (see 2).

Definition 1

An of a rooted ordered tree T is an order-preserving strictly-upward straight-line planar grid drawing $\varGamma$ of T satisfying the following properties:

• if $|V(T)|=1$, then $\varGamma$ is a grid point in the plane, representing r(T);

• otherwise, let $\varGamma _1,\dots ,\varGamma _k$ be upward canonical drawings of the subtrees $T_1,\dots ,T_k$ of r(T) (in their left-to-right order), respectively; then $\varGamma$ is such that:

  • r(T) is one unit to the left and one unit above the top-left corner of the bounding box of $\varGamma _1$;

  • the top sides of the bounding boxes of $\varGamma _1, \dots , \varGamma _k$ have the same y-coordinate; and

  • the right side of the bounding box of $\varGamma _i$ is one unit to the left of the left side of the bounding box of $\varGamma _{i+1}$, for $i=1, \dots , k-1$.

By counter-clockwise rotating an upward canonical drawing of T by $\frac{\pi }{2}$, $\pi$, and $\frac{3\pi }{2}$ radians, we obtain a , a , and a of T, respectively. A of T is an upward, leftward, downward, or rightward canonical drawing of T. In an upward, leftward, downward, or rightward canonical drawing $\varGamma$ of T, r(T) is placed at the top-left, bottom-left, bottom-right, and top-right corner of the bounding box of $\varGamma$, respectively.

Remark 4

If T has n nodes, then a canonical drawing of T lies in the 2n-box centered at r(T).

The following lemma allows us to morph one canonical drawing into another in a constant number of morphing steps.

Lemma 1

(Pinwheel). Let $\varGamma$ and $\varGamma '$ be two canonical drawings of a rooted ordered tree T, where r(T) is at the same point in $\varGamma$ and $\varGamma '$. If $\varGamma$ and $\varGamma '$ are upward and leftward, or leftward and downward, or downward and rightward, or rightward and upward, then the morph $\langle \varGamma , \varGamma ' \rangle$ is planar and lies in the interior of the right, top, left, or bottom half of the 2n-box centered at r(T), respectively.

We now describe the proof of  3. Let T be an n-node ordered tree and let $\varGamma _0$ and $\varGamma _1$ be two order-preserving straight-line planar grid drawings of T. In order to compute a morph $\mathcal {M}$ from $\varGamma _0$ to $\varGamma _1$, we root T at any leaf r(T). Since T is ordered, this determines a left-to-right order of the children of each node.

We construct three morphs: a morph $\mathcal M^0$ from $\varGamma _0$ to a canonical drawing $\varGamma _0^*$ of T, a morph $\mathcal M^1$ from $\varGamma _1$ to a canonical drawing $\varGamma ^*_1$ of T, and a morph $\mathcal M^{0,1}$ from $\varGamma _0^*$ to $\varGamma ^*_1$. Then $\mathcal M$ is composed of $\mathcal M^0$, of $\mathcal M^{0,1}$, and of the reverse of $\mathcal M^1$. The morph $\mathcal M^{0,1}$ consists of O(1) steps and can be constructed by applying 1. We describe how to construct $\mathcal M^0$; the construction of $\mathcal {M}^1$ is analogous.

Let T[0] be the tree T together with a labeling of each of the k internal nodes of T as unvisited and of each leaf as visited. We perform a bottom-up visit of T, labeling one-by-one the internal nodes of T as visited. We label a node v as visited only after all of its children have been labeled as visited. We denote by T[i] the tree T once i of its internal nodes have been labeled as visited.

Let $D_0 = \max \{w(\varGamma _0),h(\varGamma _0)\}$. Let $\varGamma$ be a drawing of T and let v be a node of T. We denote by $Large({v})$, $Med({v})$, and $Small({v})$ the $(\ell _0+4n)$-box, the $\ell _0$-box, and the 2n-box centered at v in $\varGamma$, respectively, where $\ell _0 = k_0 D_0^2n$ for some constant $k_0 > 1$ to be determined later. We have the following definition.

Fig. 3.

(a) A partially-canonical drawing $\varDelta _{i-1}$ of tree $T[i-1]$; the subtree $T^*$ lies in the gray region, visited and unvisited nodes are represented as squares and circles, respectively. (b) Drawing $\varDelta '$ of the morph $\langle \varDelta _{i-1},\varDelta '\rangle$ of 3.1.

Definition 2

An order-preserving straight-line planar grid drawing $\varGamma$ of T is a of T[i] if it satisfies the following properties ( 3a):

• (a) for each visited node u of T, the drawing $\varGamma _u$ of $T_u$ in $\varGamma$ is upward canonical or downward canonical; further, if $u\ne r(T)$, then $\varGamma _u$ is upward canonical, if $y_\varGamma (u) \le y_\varGamma (p(u))$, or downward canonical, if $y_\varGamma (u) > y_\varGamma (p(u))$;

• (b) for each edge $e=(v,u)$ of T, where v is the parent of u and v is unvisited, there exists a sector $S_e$ of a circumference centered at v such that:

  • (b.i) $S_e$ encloses $Small({u})$;

  • (b.ii) $S_e$ contains no node with the exception of v and of, possibly, the nodes of $T_u$, and no edge with the exception of (u, v) and of, possibly, the edges of $T_u$;

  • (b.iii) the intersection between $S_e$ and $Med({v})$ contains a 2n-box $B_u$ whose corners have integer coordinates and whose center $c_u$ is such that $y_\varGamma (c_u) \le y_\varGamma (v)$ if and only if $y_\varGamma (u) \le y_\varGamma (v)$; and

  • (b.iv) for any edge $e' \ne e$ incident to v, the sectors $S_e$ and $S_{e'}$ are internally disjoint;

• (c) for any two nodes v and w, it holds $Large({v}) \cap Large({w}) = \emptyset$; and

• (d) for each node v of T, $Large({v})$ contains no node different from v, and any edge e or any sector $S_e$ intersecting $Large({v})$ is such that e is incident to v.

Note that, by Property (a), a partially-canonical drawing of T[k] is a canonical drawing.

The algorithm to construct $\mathcal M^0$ is as follows. First, we scale $\varGamma _0$ up by a factor in $O(D_0^3n)$ so that the resulting drawing $\varDelta _0$ is a partially-canonical drawing of T[0] (see 2). Clearly, the morph $\mathcal M_0 = \langle \varGamma _0, \varDelta _0 \rangle$ is planar, $w(\mathcal M_0) = w(\varDelta _0)$, and $h(\mathcal M_0) = h(\varDelta _0)$.

For $i=1,\dots , k$, let $v_i$ be the node that is labeled as visited at the i-th step of the bottom-up visit of T. Starting from a partially-canonical drawing $\varDelta _{i-1}$ of $T[i-1]$, we construct a partially-canonical drawing $\varDelta _{i}$ of T[i] and a morph $\mathcal M_{i-1,i}$ from $\varDelta _{i-1}$ to $\varDelta _{i}$ with $O(\deg (v_i))$ steps, with $w(\mathcal M_{i-1,i}) = w(\varDelta _{i-1})$ and $h(\mathcal M_{i-1,i}) = h(\varDelta _{i-1})$ (see  3).

Composing $\mathcal M_0, \mathcal M_{0,1},\mathcal M_{1,2},\dots ,\mathcal M_{k-1,k}$ yields the desired morph $\mathcal M^0$ from $\varGamma _0$ to a canonical drawing $\varDelta _k=\varGamma ^*_0$ of T. The morph has $\sum _i deg(v_i)\in O(n)$ steps (by 3). Further, $w(\mathcal M^0) = w(\varDelta _0)$ and $h(\mathcal M^0) = h(\varDelta _0)$ (by  3), hence $w(\mathcal M^0) \in O(D^3_0n \cdot w(\varGamma _0))$ and $h(\mathcal M^0) \in O(D^3_0n \cdot h(\varGamma _0))$ (by  2).

Lemma 2

There is an integer $B_0 \in O(D^3_0n)$ such that the drawing $\varDelta _0$ obtained by scaling the drawing $\varGamma _0$ of T up by $B_0$ is a partially-canonical drawing of T[0].

Lemma 3

For any $i\in \{1,\dots ,k\}$, let $\varDelta _{i-1}$ be a partially-canonical drawing of $T[i-1]$. There exists a partially-canonical drawing $\varDelta _i$ of T[i] and an $O(\deg (v_i))$-step planar morph $\mathcal M_{i-1,i}$ from $\varDelta _{i-1}$ to $\varDelta _{i}$ such that $w(\mathcal M_{i-1,i}) \le w(\varDelta _0) + \ell _0 + 4n$ and $h(\mathcal M_{i-1,i}) \le h(\varDelta _0) + \ell _0 + 4n$.

The rest of the section is devoted to the proof of 3. We denote by $T^*$ the tree obtained by removing from T the nodes of $T_{v_i}$ and their incident edges. Let $\varDelta _i$ be the straight-line drawing of T obtained from $\varDelta _{i-1}$ by redrawing $T_{v_i}$ so that it is upward canonical, if $y_{\varDelta _{i-1}}(v_i) \le y_{\varDelta _{i-1}}(p(v_i))$, or downward canonical, otherwise, while keeping the placement of $v_i$ and of every node of $T^*$ unchanged.

Lemma 4

The drawing $\varDelta _i$ is a partially-canonical drawing of T[i].

We show how to construct a morph $\mathcal M_{i-1,i}$ from $\varDelta _{i-1}$ to $\varDelta _i$ satisfying the properties of the statement of the lemma. This is done in several stages as follows.

First, consider the drawing $\varDelta '$ of T obtained as described next; refer to 3b. Initialize $\varDelta '=\varDelta _{i-1}$. Then, for each child u of $v_i$, translate the drawing of $T_{u}$ so that u is at the center of a 2n-box $B_u$ that lies in the intersection between $S_e$ and $Med({v_i})$, whose corners have integer coordinates, and whose center $c_u$ is such that $y_{\varDelta _{i-1}}(c_u) \le y_{\varDelta _{i-1}}(v_i)$ if and only if $y_{\varDelta _{i-1}}(u) \le y_{\varDelta _{i-1}}(v_i)$; such a box exists by Property (b.iii) of $\varDelta _{i-1}$. Also, redraw the edge $(v_i,u)$ as a straight-line segment in $\varDelta '$.

Claim 3.1

The morph $\langle \varDelta _{i-1},\varDelta '\rangle$ is planar.

Fig. 4.

Regions for $v_i$.

Second, we show how to move the subtrees rooted at the children of $v_i$ in the interior of $Large({v_i})$, so that they land in the position they have in $\varDelta _i$. The way we deal with such subtrees depends on their placement with respect to $v_i$ and to the drawing of edge $(v_i,p(v_i))$. We consider the case in which $y(p(v_i))\ge y(v_i)$ and $x(p(v_i)) \ge x(v_i)$; the other cases can be treated similarly. In particular, we distinguish four regions $\mathcal R_1$, $\mathcal R_2$, $\mathcal R_3$, and $\mathcal R_4$ defined as follows; refer to 4. Let $h_\rightarrow (v)$ and $h_\leftarrow (v)$ be the horizontal rays originating at a node v and directed rightward and leftward, respectively. Further, let $h_\uparrow (v)$ be the horizontal ray originating at a node v and directed upward.

Fig. 5.

Illustrations for 3, focused on the children of $v_i$ that lie in $\mathcal R_2$.

• Region $\mathbf {\mathcal R_1}$ is defined as the intersection of $Med({v_i})$ with the wedge centered at $v_i$ obtained by counter-clockwise rotating $h_\rightarrow (v_i)$ until it passes through $p(v_i)$; note that, if $(v_i,p(v_i))$ is a horizontal segment, then $\mathcal R_1=\emptyset$.

• Region $\mathbf {\mathcal R_2}$ is the rectangular region that is the lower half of $Med({v_i})$;

• Region $\mathbf {\mathcal R_3}$ is defined as the intersection of $Med({v_i})$ with the wedge centered at $v_i$ obtained by clockwise rotating $h_\leftarrow (v_i)$ until it coincides with $h_\uparrow (v_i)$; and

• Region $\mathbf {\mathcal R_4}$ is defined as the intersection of $Med({v_i})$ with the wedge centered at $v_i$ obtained by clockwise rotating $h_\uparrow (v_i)$ until it passes through $p(v_i)$; note that, if $(v_i,p(v_i))$ is a vertical segment, then $\mathcal R_4=\emptyset$.

Note that $Med({v_i})=\mathcal R_1 \cup \mathcal R_2 \cup \mathcal R_3 \cup \mathcal R_4$.

We define two more regions (see 4), which will be exploited as “buffers” that allow us to rotate subtrees via 1 without introducing crossings. Let $\mathcal S_L$ and $\mathcal S_R$ be the rectangular regions in $\varDelta '$ containing all the points in $Large({v_i}) - Med({v_i})$ to the left of the left side of $Med({v_i})$ and to the right of the right side of $Med({v_i})$, respectively. Observe that, since $\varDelta _{i-1}$ satisfies Property (d) of a partially-canonical drawing and by the construction of $\varDelta '$, the region $\mathcal S_L$ is empty, while the region $\mathcal S_R$ may only be traversed by the edge $(v_i, p(v_i))$.

We start by dealing with the children $u_j$ of $v_i$ that lie in the interior of $\mathcal R_2$; refer to 5. Consider the edges $(v_i,u_j)$ in the order $(v_i,u_1),(v_i,u_2),\dots , (v_i,u_m)$ in which such edges are encountered while clockwise rotating $h_\rightarrow (v_i)$; see 5a. Let $\varPsi _1$ be the drawing obtained from $\varDelta '$ by translating the drawing of the tree $T_{u_1}$ so that $u_1$ lies in the interior of $\mathcal S_R$ and one unit below $v_i$ and so that the right side of the bounding box of the drawing of $T_{u_1}$ lies upon the right side of $Large({v_i})$, and by redrawing the edge $(v_i,u_1)$ as a straight-line segment.

Claim 3.2

The morph $\langle \varDelta ',\varPsi _1\rangle$ is planar.

For $j=2,\dots ,m$, let $\varPsi _j$ be the drawing obtained from $\varPsi _{j-1}$ by translating the drawing of the tree $T_{u_j}$ so that $u_j$ lies in the interior of $\mathcal S_R$ and one unit below $v_i$ and so that the right side of the bounding box of the drawing of $T_{u_j}$ lies one unit to the left of $u_{j-1}$, and by redrawing the edge $(v_i,u_j)$ as a straight-line segment.

Claim 3.3

For $j=2,\dots ,m$, the morph $\langle \varPsi _{j-1},\varPsi _j\rangle$ is planar.

Let $\varDelta ^+$ be the drawing obtained from $\varPsi _m$ by horizontally translating $T_{u_j}$ so that $u_j$ lands at its final position in $\varDelta _i$, and by redrawing the edge $(v_i,u_j)$ as a straight-line segment, for $j=1,2,\dots ,m$; see 5c and d.

Claim 3.4

The morph $\langle \varPsi _m,\varDelta ^+\rangle$ is planar.

Fig. 6.

Illustrations for 3, focused on the children of $v_i$ that lie in $\mathcal R_1$.

Next, we deal with the children $u_j$ of $v_i$ that lie in the interior of $\mathcal R_1$. Consider the edges $(v_i,u_j)$ in the order $(v_i,u_1),(v_i,u_2),\dots , (v_i,u_\ell )$ in which such edges are encountered while counter-clockwise rotating $h_{\rightarrow }(v_i)$ around $v_i$; refer to 6. We are going to move the subtrees rooted at the children of $v_i$ in $\mathcal R_1$, one by one in the order $T_{u_1},T_{u_2},\dots ,T_{u_\ell }$, so that they land in the position that they have in $\varDelta _i$. Such a movement consists of four linear morphs. First, we rotate the drawing of $T_{u_j}$ so that it becomes leftward canonical (see 6b). Second, we translate the drawing of $T_{u_j}$ so that $u_j$ lies in the interior of $S_R$ and one unit below $v_i$ (see 6c). Third, we rotate the drawing of $T_{u_j}$ so that it becomes upward canonical (see 6d). Finally, we horizontally translate the drawing of $T_{u_j}$ to its final position in $\varDelta _i$ (see 6e).

We now provide the details of the above four linear morphs. For $j=1,\dots ,\ell$, let $\xi _{j-1}^{4}$ be a drawing of T with the following properties, where $\xi _0^{4} = \varDelta ^+$ (refer to 6a and e): (P1) the drawing of $T^*$ is the same as in $\varDelta _i$; (P2) $v_i$ lies at the same point as in $\varDelta _i$; (P3) the drawing of the subtrees of the children of $v_i$ belonging to $\mathcal R_2$ (in $\varDelta '$), and the drawing of the subtrees $T_{u_1},T_{u_2}, \dots ,T_{u_{j-1}}$ is the same as in $\varDelta _i$; (P4) the drawing of the subtrees $T_{u_{j}},T_{u_{j+1}}, \dots , T_{u_\ell }$ is the same as in $\varDelta ^+$; and (P5) the drawing of the subtrees rooted at the children of $v_i$ that lie in the interior of $\mathcal R_3$ and $\mathcal R_4$ is the same as in $\varDelta ^+$.

For $j=1,\dots ,\ell$, we construct a drawing $\xi _j^{1}$ from $\xi _{j-1}^{4}$ by rotating tree $T_{u_j}$ so that it is leftward canonical in $\xi _j^{1}$, and by leaving the position of the nodes not in $T_{u_j}$ unaltered. This rotation can be accomplished via a linear morph $\langle \xi _{j-1}^{4}, \xi _j^{1}\rangle$ by 1; see 6b.

Claim 3.5

For $j=1,\dots ,\ell$, the morph $\langle \xi _{j-1}^{4}, \xi _j^{1}\rangle$ is planar.

For $j=1,\dots ,\ell$, let $\xi _j^{2}$ be the drawing obtained from $\xi _j^{1}$ by translating the drawing of $T_{u_j}$ so that $Small({u_j})$ lies in the interior of $\mathcal S_R$ and so that $u_j$ lies one unit below $v_i$, and by redrawing the edge $(v_i,u_j)$ as a straight-line segment; see 6c.

Claim 3.6

For $j=1,\dots ,\ell$, the morph $\langle \xi ^1_j,\xi ^2_j\rangle$ is planar.

For $j=1,\dots ,\ell$, let $\xi _j^{3}$ be the drawing obtained from $\xi _{j}^{2}$ by rotating tree $T_{u_j}$ so that it is upward canonical in $\xi _j^{3}$, and by leaving the position of the nodes not in $T_{u_j}$ unaltered. This rotation can be accomplished via a linear morph $\langle \xi _{j}^{2}, \xi _j^{3}\rangle$, by 1; see 6d.

Claim 3.7

For $j=1,\dots ,\ell$, the morph $\langle \xi _{j}^{2}, \xi _j^{3}\rangle$ is planar.

Finally, for $j=1,\dots ,\ell$, let $\xi _j^{4}$ be the drawing obtained from $\xi _{j}^{3}$ by horizontally translating $T_{u_j}$ so that $u_j$ lies at its final position in $\varDelta _i$, and by leaving the position of the nodes not in $T_{u_j}$ unaltered; see 6e.

Claim 3.8

For $j=1,\dots ,\ell$, the morph $\langle \xi _{j}^{3}, \xi _j^{4}\rangle$ is planar.

Note that the drawing $\xi ^4_\ell$ coincides with $\varDelta _{i}$, except for the drawing of the subtrees lying in the interior of $\mathcal R_3$ and $\mathcal R_4$.

Subtrees in $\mathcal R_3$ are treated symmetrically to the ones in $\mathcal R_1$. In particular, the subtrees of the children of $v_i$ that lie in $\mathcal R_3$ are processed according to the clockwise order of the edges from $v_i$ to their roots, while the role played by $\mathcal S_R$ is now assumed by $\mathcal S_L$.

The treatment of the subtrees in $\mathcal R_4$ is similar to the one of the subtrees in $\mathcal R_3$. However, when a subtree is considered, it is first horizontally translated in the interior of $\mathcal R_3$ and then processed according to the rules for such a region.

Altogether, we have described a morph $\mathcal M_{i-1,i}$ from the partially-canonical drawing $\varDelta _{i-1}$ of $T[i-1]$ to $\varDelta _i$, which is a partially-canonical drawing of T[i] by 4. Next, we argue about the properties of $\mathcal M_{i-1,i}$.

We deal with the area requirements of $\mathcal M_{i-1,i}$. Consider the drawing $\varDelta _0$ and place the boxes $Large({v})$ around the nodes v of T; the bounding box of the arrangement of such boxes has width $w(\varDelta _0)+\ell _0+4n$ and height $h(\varDelta _0)+\ell _0+4n$. We claim that the drawings of $\mathcal M_{i-1,i}$ lie inside such a bounding box. Assume this is true for $\varDelta _{i-1}$ (this is indeed the case when $i=1$); all subsequent drawings of $\mathcal M_{i-1,i}$ coincide with $\varDelta _{i-1}$, except for the placement of the subtrees rooted at the children of $v_i$, which however lie inside $Large({v_i})$ in each of such drawings. Since $v_i$ has the same position in $\varDelta _{i}$ as in $\varDelta _0$ and since $Large({v_i})$ has width and height equal to $\ell _0+4n$, the claim follows.

Finally, we deal with the number of linear morphs composing $\mathcal M_{i-1,i}$. The morph $\mathcal M_{i-1,i}$ consists of the morph $\langle \varDelta _{i-1},\varDelta '\rangle$, followed by the morphs needed to drive the subtrees rooted at the children of $v_i$ to their final positions in $\varDelta _i$. Since the number of morphing steps needed to deal with each of such subtrees is constant, we conclude that $M_{i-1,i}$ consists of $O(\deg (v_i))$ linear morphing steps. This concludes the proof of 3.

5 Conclusions and Open Problems

We presented an algorithm that, given any two order-preserving straight-line planar grid drawings $\varGamma _0$ and $\varGamma _1$ of an n-node ordered tree T, constructs a morph $\langle \varGamma _0=\varDelta _0,\varDelta _1,\dots ,\varDelta _{k}=\varGamma _1\rangle$ such that k is in O(n) and such that the area of each intermediate drawing $\varDelta _i$ is polynomial in n and in the area of $\varGamma _0$ and $\varGamma _1$. Better bounds can be achieved if T is rooted and $\varGamma _0$ and $\varGamma _1$ are also strictly-upward drawings, especially in the case in which T is a binary tree.

We make a remark about the generality of the model that we adopted. At a first glance, our assumption that $\varGamma _0$ and $\varGamma _1$ are grid drawings seems restrictive, and it seems more general to consider drawings that have bounded resolution. However, by using an observation from [9], one can argue that two morphing steps suffice to transform a drawing with resolution r in a grid drawing whose area is polynomial in r. Namely, it suffices to scale each input drawing so that the smallest distance between any pair of geometric objects (points representing vertices or segments representing edges) is 2; this is a single morphing step which does not change the resolution of the drawing, hence the largest distance between any pair of geometric objects is in O(r). Then each node can be moved to the nearest grid point; this is another morphing step, which is ensured to be planar by the fact that each node moves by at most $\sqrt{2}/2$, hence this motion only brings any two geometric objects closer by $\sqrt{2}$, while their distance is at least 2. Thus, this results in a grid drawing on an $O(r)\times O(r)$ grid.

Several problems are left open. Is it possible to generalize our results to graph classes richer than trees? Is it possible to improve our area bounds for morphs of straight-line planar grid drawings of trees or even just of paths? Is there a trade-off between the number of steps and the area required by a morph? Are there other relevant tree drawing standards for which it makes sense to consider the morphing problem?