On Morphing 1-Planar Drawings

Abstract

Computing a morph between two drawings of a graph is a classical problem in computational geometry and graph drawing. While this problem has been widely studied in the context of planar graphs, very little is known about the existence of topology-preserving morphs for pairs of non-planar graph drawings. We make a step towards this problem by showing that a topology-preserving morph always exists for drawings of a meaningful family of 1-planar graphs. While our proof is constructive, the vertices may follow trajectories of unbounded complexity.

This work was partially supported by the Department of Engineering, University of Perugia, grants RICBA19FM and RICBA20ED and by DFG grant KA812/18-1.

1 Introduction

Computing a morph between two drawings of the same graph is a classical problem that attracted considerable attention over the years, also in view of its numerous applications in computer graphics and animations (refer to [1] for a short overview). At high level, given two drawings $\varGamma _a(G)$ and $\varGamma _b(G)$ of the same graph G, a morph between $\varGamma _a(G)$ and $\varGamma _b(G)$ is a continuously changing family of drawings such that the initial one coincides with $\varGamma _a(G)$ and the final one with $\varGamma _b(G)$. A standard assumption is that the two input drawings - as well as all intermediate ones - are topologically equivalent, i.e., they define the same set of cells (see Sect. 2 for formal definitions). The main challenge is to design morphing algorithms that maintain some additional geometric properties of the input drawings throughout the transformation, such as planarity with straight-line edges (see, e.g., [1, 16, 25]), convexity [6, 34], orthogonality [12, 26], and upwardness [20]. We point the reader to [4, 8, 10, 11] for additional related work.

In this context, the most prominent research direction focuses on morphs of straight-line planar drawings: The topological equivalence condition implies that all drawings in the morph have the same planar embedding; in addition, it is also required that edges remain straight-line segments. Back in 1944, Cairns [16] proved that such morphs always exist if the input graphs are plane triangulations. This implies that, for a fixed plane triangulation, the space of its straight-line planar drawings is connected. The main drawback of Cairns result is in the underlying construction, which involves exponentially-many morphing steps. The extension of Cairns’ result to all plane graphs was initially done by Thomassen [34], while later Floater and Gotsman [25], and Gotsman and Surazhsky [27, 32] proposed different approaches using trajectories of unbounded complexity. More recently, Alamdari et al. [2] focused on the complexity of the morph. They described the first morphing algorithm for planar straight-line drawings that makes use of a polynomial number of steps, where in each step vertices move at uniform speed along linear trajectories. In a subsequent paper [1], a linear bound on the number of steps is shown, which is worst-case optimal.

Morphing non-planar drawings of graphs appears to be a more elusive problem. In particular, Angelini et al. [5] asked whether a morphing algorithm exists for pairs of non-planar straight-line drawings such that the topology of the crossings in the drawing is maintained throughout the morph. They stressed that a solution to this problem is not known even if the vertex trajectories are allowed to have arbitrary complexity. Note that the obvious idea of morphing the “planarizations” of the drawings (i.e., the planar drawings obtained by treating crossings as dummy vertices) does not trivially work. Namely, in order to guarantee that edges remain straight-line segments throughout the morph, one has to ensure that opposite edges incident to dummy vertices maintain the same slope. To the best of our knowledge, such requirement cannot be easily incorporated into any of the already known morphing algorithms for planar graphs.

One way of simplifying the problem is to consider graphs that are non-planar but still admit embeddings on surfaces of bounded genus. Chambers et al. [17] proved the existence of morphs for pairs of crossing-free drawings on the Euclidean flat torus (edges are still geodesics). Their technique is complex and the authors concluded that an extension to higher genus surfaces is fairly non-trivial.

We make a step towards settling the open problem in [5] by studying non-planar drawings of graphs with forbidden edge-crossing patterns. Our focus is on the family of 1-planar graphs, which naturally extends the notion of planarity by allowing each edge to be crossed at most once (see [29] for a survey). Note that 1-planar graphs form a well studied family of non-planar graphs with early results dating back to the 60’s [9, 31], while more recently they have gained considerable attention in the rapidly growing literature about beyond planarity [23, 28].

Fig. 1.

Two topologically-equivalent kite-planar $1$-planar drawings of the same graph.

Our Contribution. We provide a set of sufficient conditions under which any pair of 1-planar straight-line drawings admits a morph. At high-level, we require that if two edges cross, then they can be enclosed in a quadrilateral region whose boundary is uncrossed; although this region may contain further vertices in its interior, we require that any edge connecting an end-vertex of the crossing edges to a vertex inside the region is also uncrossed; refer to Fig. 1 for an illustration. A drawing that satisfies these requirements is called kite-planar 1-planar (see Definition 1). Our main result is summarized by the following theorem.

Theorem 1

There exists a morph between any pair of topologically-equivalent kite-planar $1$-planar drawings.

Theorem 1 implies that, for a fixed graph, the space of its topologically-equivalent kite-planar $1$-planar drawings is connected. The proof is constructive, although the vertices may use trajectories of unbounded complexity. Concerning the definition of kite-planar $1$-planar drawings, it may be worth observing that, due to a simple edge density argument, the graphs admitting such a drawing cannot be embedded on any surface of bounded genus. Indeed, as shown in Sect. 6, some well-known families of 1-planar graphs admit drawings that are kite-planar $1$-planar and require arbitrary large genus to be embedded.

Paper Structure. Section  2 contains basic definitions and notation. Section 3 gives an overview of the proof technique, which exploits a recursive construction. The base case of the recursion is described in Sect. 4, while the recursive step is in Sect. 5. Implications of our result in terms of classes of 1-planar drawings that admit a morph are discussed in Sect. 6. Open problems are given in Sect. 7. For space reasons, the proofs of the statements marked with ($\diamond$) are omitted.

2 Preliminaries

Drawings. A straight-line drawing (or simply a drawing, for short) $\varGamma (G)$ of a graph G maps each vertex v of G to a distinct point $p_v$ of the plane and each edge (u, v) of G to a straight-line segment connecting $p_u$ and $p_v$ without passing through any other point representing a vertex of G. When this creates no ambiguities, we will not distinguish between a vertex and the point representing it in $\varGamma (G)$, as well as between an edge and its segment. Note that, by definition, two edges of a drawing share at most one point, which is either a common endpoint or an interior point where the two edges properly cross. Drawing $\varGamma (G)$ partitions the plane into connected regions called cells. The boundary of a cell consists of vertices, crossing points, and (parts of) edges. The external cell of $\varGamma (G)$ is its (only) unbounded cell. Two drawings $\varGamma _a(G)$ and $\varGamma _b(G)$ of the same graph G are topologically equivalent if they define the same set of cells up to an orientation-preserving homeomorphism of the plane. An embedding of G is an equivalence class of drawings that are pairwise topologically equivalent.

A drawing $\varGamma (G)$ is planar if no two edges cross. In this case, the cells of $\varGamma (G)$ are called faces and their boundaries consist of just vertices and edges. A graph is planar if it admits a planar drawing. A planar graph together with an embedding defined by a planar drawing is a plane graph. A planar drawing is strictly convex if all its faces are strictly convex polygons.

A graph is 1-planar if it admits a (not necessarily straight-line) 1-planar drawing in which every edge crosses at most one other edge. A 1-planar graph together with an embedding defined by a 1-planar drawing is a 1-plane graph. A kite K in a 1-planar drawing $\varGamma (G)$ is a 1-planar drawing of $K_4$ in $\varGamma (G)$ whose external cell is a quadrilateral. The four edges on the boundary of the external cell of K are called kite edges. The other two edges are the crossing edges of K and are drawn inside the quadrilateral bounding K. Figure 1 shows three kites; the kite (crossing) edges are fat blue (dashed-dotted red, resp.).

Given a vertex v of G and a kite K, the following exclusive cases can occur: (i) v belongs to K, if it is a vertex of the $K_4$ defining K, or (ii) v is inside K (or K contains v) if v lies in the interior of the quadrilateral bounding K, or (iii) v is outside K, otherwise. A kite is empty if it contains no vertex; otherwise, it is non-empty. An edge (u, v) is a binding edge (dashed green in Fig. 1) if u belongs to a non-empty kite K and v is inside K. We can now introduce kite-planar $1$-planar drawings.

Definition 1

A straight-line drawing is kite-planar 1-planar, or 1-kite-planar for short, if: (P.1) every edge is crossed at most once, (P.2) the four kite edges of every kite are present and uncrossed, and (P.3) every binding edge is uncrossed.

Let $\varGamma (G)$ be a $1$-kite-planar drawing of G. We say that a vertex of G is of level 0 if no kite contains it, while it is of level $i>0$ if the maximum level of the vertices belonging to a kite containing it is $i-1$. In Fig. 1, the black (white) vertices are of level 0 (level 1, resp.). The next property follows from P.3 of Definition 1.

Property 1

($\diamond$). If two vertices belong to the same kite of a $1$-kite-planar drawing $\varGamma (G)$, then they are of the same level.

Morphs. Let $\varGamma _a(G)$ and $\varGamma _b(G)$ be two topologically-equivalent drawings of the same graph G. A morph between them is a continuously changing family of pairwise topologically-equivalent drawings of G indexed by time $t \in [0, 1]$, such that the drawing at time $t = 0$ is $\varGamma _a(G)$ and the drawing at time $t = 1$ is $\varGamma _b(G)$. Since edges are drawn as straight-line segments, a morph is uniquely specified by the vertex trajectories. Also, during the course of the morph, a vertex may coincide with neither another vertex nor an internal point of an edge.

3 Outline of the Proof of Theorem 1

In this section, we give an outline of the proof of Theorem 1, namely, that there exists a morph between any two topologically-equivalent $1$-kite-planar drawings $\varGamma _a(G)$ and $\varGamma _b(G)$ of a graph G. Recall that $\varGamma _a(G)$ and $\varGamma _b(G)$ define the same embedding of G. Hence, G is necessarily a 1-plane graph.

Our proof is by means of a recursive construction. The underlying idea is to compute a morph by keeping each kite boundary drawn as a strictly-convex polygon, so that, in the course of the morph, the drawing of the corresponding crossing edges will stay inside their boundary. The main challenge, however, stems from the fact that a kite may not be empty. Therefore, our approach is to remove the interior of each kite, recursively compute a morph that keeps the convexity of the kite boundaries, and suitably reinsert (and morph) the removed subdrawings. In the proof, we will use two key ingredients. The first one is a result by Aronov et al. [7], which guarantees that one can compatibly triangulate two topologically-equivalent planar drawings of a planar graph.

Theorem 2

(Aronov et al. [7]). Given two topologically-equivalent planar drawings $\varGamma _a(P)$ and $\varGamma _b(P)$ of the same n-vertex planar graph P, it is possible to augment $\varGamma _a(P)$ and $\varGamma _b(P)$ to two topologically-equivalent planar drawings $\varGamma _a(P')$ and $\varGamma _b(P')$ of the same maximal planar graph $P'$ such that $\varGamma _a(P) \subseteq \varGamma _a(P')$, $\varGamma _b(P) \subseteq \varGamma _b(P')$, and the order of $P' \setminus P$ is $O(n^2)$.

The second ingredient is a result by Angelini et al. [6], which allows us to morph a pair of convex drawings by preserving the convexity of the faces. The main properties of this result are summarized in the next theorem.

Theorem 3

(Angelini et al. [6]). Let $\langle \varGamma _a(P), \varGamma _b(P) \rangle$ be a pair of topologically-equivalent strictly-convex planar drawings of a graph P. There is a morph between $\varGamma _a(P)$ and $\varGamma _b(P)$ in which every intermediate drawing is strictly convex. If the outer face of G has only three vertices and each of them has the same position in $\varGamma _a(P)$ and $\varGamma _b(P)$, then these three vertices do not move during this morph.

We apply recursion on the maximum level $\ell$ of a vertex of G. The base case ($\ell =0$) is described in Sect. 4, while the recursive case ($\ell >0$) in Sect. 5.

4 Base Case

In the base case of the recursion, all the vertices of G are of level 0, which implies that all the kites of G, if any, are empty. Let P be the graph obtained by removing both crossing edges from each kite of G. Let $\langle \varGamma _a(P), \varGamma _b(P) \rangle$ be the restrictions of $\langle \varGamma _a(G), \varGamma _b(G) \rangle$ to P, respectively; see Fig. 2. By construction, $\langle \varGamma _a(P), \varGamma _b(P) \rangle$ is a pair of planar and topologically-equivalent drawings, and P is a plane subgraph of G. The kite edges of each kite K of G are uncrossed (by P.2 of Definition 1) and bound a quadrangular face $f_K$ in P, which we call marked.

Let $P'$ and $\langle \varGamma _a(P'), \varGamma _b(P') \rangle$ be the graph and the corresponding pair of planar drawings obtained by applying Theorem 2 to $\langle \varGamma _a(P), \varGamma _b(P) \rangle$, except for the marked faces; see Fig. 2 for an illustration. This operation guarantees that every face in both drawings is a triangle, if not marked, or a quadrangle, if marked. We call a plane graph with such faces almost triangulated, and we next prove that it is triconnected.

Fig. 2.

Illustration of the transitions $\varGamma _a(G) \rightarrow \varGamma _a(P) \rightarrow \varGamma _a(P')$; marked faces are gray.

Lemma 1

Every almost triangulated plane graph is triconnected.

Proof

Let $P'$ be an almost triangulated plane graph derived from a $1$-kite-planar drawing of a 1-planar graph G. Suppose that $P'$ contains a separation pair $\{u,v\}$. Then there exist at least two faces $f_1$ and $f_2$ that are incident to both u and v such that at least one, say $f_2$, is not triangular, by simplicity, and hence is marked with u and v not adjacent. Hence, the edge (u, v) exists in G and not in $P'$. Consequently, $f_1$ cannot be a triangle, as otherwise it would contain edge (u, v) on its boundary. On the other hand, if $f_1$ is marked, then G contains another copy of (u, v) drawn inside the kite that yielded $f_1$, which is impossible since G is simple. Hence, $P'$ contains no separation pair. The absence of cutvertices stems from the fact that each face is either a triangle or a quadrangle (if marked).    $\square$

Since each kite contains two crossing edges in G, its boundary is drawn strictly convex in both $\varGamma _a(G)$ and $\varGamma _b(G)$. Hence, $\varGamma _a(P')$ and $\varGamma _b(P')$ are two strictly convex planar drawings of $P'$. This property allows to apply Theorem 3 to compute a morph of $\langle \varGamma _a(P'), \varGamma _b(P') \rangle$ that maintains the strict convexity of the drawing at any time instant. Since each marked face $f_K$ remains strictly convex, adding back the two crossing edges of the corresponding kite K in $P'$ yields a morph of a supergraph of G (and thus of G) in which these crossing edges remain inside the boundary of K at any time instant. This concludes the base case.

5 Recursive Case

In this section, we focus on the recursive step of the proof of Theorem 1, in which the maximum level of a vertex in G is $\ell > 0$. Let Q be the graph obtained by removing all the vertices of level $\ell$ from G, and let $\langle \varGamma _a(Q),\varGamma _b(Q) \rangle$ be the restriction of $\langle \varGamma _a(G),\varGamma _b(G)\rangle$ to Q. Clearly, the two drawings of Q are topologically equivalent and the maximum level of a vertex is $\ell -1$. Thus, we can recursively compute a morph of $\langle \varGamma _a(Q),\varGamma _b(Q) \rangle$. In what follows, we describe how to incorporate the trajectories of the level-$\ell$ vertices into the morph of $\langle \varGamma _a(Q),\varGamma _b(Q) \rangle$, so to obtain the desired morph of $\langle \varGamma _a(G),\varGamma _b(G)\rangle$.

Setting Up the Morph. We begin by observing that, by Property 1, each vertex of level $\ell$ is contained in a kite whose vertices are all of level $\ell -1$, which implies that this kite is empty in Q (but not in G). Consider such a kite K, and note that its two crossing edges define four triangular regions that remain non-degenerate during the morph of $\langle \varGamma _a(Q),\varGamma _b(Q)\rangle$. We refer to each of these four triangular regions as a piece of a kite. The natural idea of applying recursion to every piece of a kite does not work, since the algorithm in [6] does not allow prescribing the trajectories of the vertices of the outer face, which would be required in the base case of this approach. Thus, we describe a more elaborated approach.

Consider a piece of kite K and denote it by $\triangle$. The unique edge (u, v) of $\triangle$ that belongs to the boundary of K is called the base edge of $\triangle$. Since $\triangle$ remains non-degenerate during the morph, there exists a half-disk D that, throughout the whole morph, has the following properties (see also Fig. 3 for an illustration):

• half-disk D lies in $\triangle$ and is centered at the midpoint w of (u, v), and

• the length of its radius is positive and it does not change.

Fig. 3.

Illustration of the half-disk D of $\triangle$ and their geometric properties.

Let $\lambda$ be the smallest length of the base edge (u, v) during the morph, let r be the radius of D perpendicular to (u, v), and let $w'$ be the endpoint of r different from w. Also, denote by $t^*$ any time instant of the morph when the length of (u, v) equals $\lambda$, and let $\phi$ be the internal angle at $w'$ of the triangle formed by u, w and $w'$ at time $t^*$. In particular, $\phi$ satisfies $\tan (\phi ) = \frac{\lambda }{2} \cdot \frac{1}{|r|}$.

Consider the graph $\mathcal {H} = G \setminus Q$ induced by the level-$\ell$ vertices of G, and let $H_{\triangle }$ be the subgraph of $\mathcal H$ that lies inside $\triangle$. We proceed to compute a drawing of $H_{\triangle }$ that, intuitively, will be “small” enough to fit inside D and “skinny” enough to avoid crossings with the binding edges that connect u or v to $H_{\triangle }$. To ease the notation, from now on we will refer to $H_{\triangle }$ as H.

To compute this drawing, we first augment H as well as its drawings in $\langle \varGamma _a(G), \varGamma _b(G) \rangle$, as follows. We add a dummy vertex d connected to u and to v, which is drawn sufficiently close to the crossing point of the two diagonals of K in both $\varGamma _a(G)$ and $\varGamma _b(G)$, so that the triangle formed by u, v, and d contains H.

As in the transition from P to $P'$ in Sect. 4, we remove the crossing edges of every (empty) kite of $H \cup \{u,v,d\}$ and we mark the resulting quadrangular face. Then we apply Theorem 2 to the resulting planar subgraph of $H \cup \{u,v,d\}$ and to its drawings in $\langle \varGamma _a(G), \varGamma _b(G) \rangle$, except for its marked faces. This results in an almost triangulated plane graph $H'$ and in a pair of topologically-equivalent strictly convex drawings $\langle \varGamma _a(H'),\varGamma _b(H') \rangle$ of $H'$. The following observation is directly implied by Property P.3 of Definition 1.

Observation 1

Every face incident to u or to v in $H'$ is triangular.

Consider the plane graph obtained from $H'$ by removing u and v, and let $\mathcal C$ be the graph formed by the vertices and the edges of its outer face. In the following lemma, we investigate some properties of $\mathcal C$. The BC-tree $\mathcal {T}$ of a connected graph G represents the decomposition of G into its biconnected components, called blocks. Namely, $\mathcal {T}$ has a B-node for each block of G and a C-node for each cutvertex of G, such that each B-node is connected to the C-nodes that are part of its block.

Lemma 2

($\diamond$). The following properties of $\mathcal C$ hold: (i) $\mathcal C$ is outerplane and connected. (ii) Each block of $\mathcal C$ is a cycle, possibly degenerated to a single edge. (iii) Every cutvertex of $\mathcal C$ is connected to both u and v in $H'$. (iv) The BC-tree of $\mathcal C$ is a path. (v) Every non cutvertex of $\mathcal C$ is connected to exactly one of u and v in $H'$, with the exception of exactly two vertices (one of them is d) which belong to the blocks of $\mathcal C$ corresponding to degree-1 B-nodes in the BC-tree of $\mathcal C$.

In view of Properties (ii) and (iv) of Lemma 2, we refer to $\mathcal C$ as a chain of cycles and to its blocks as cycles, even when degenerated to single edges. Moreover, we denote by $d'$ the non cutvertex of $\mathcal C$ different from d that is incident to both u and v, as specified in Property (v) of Lemma 2.

Making Each Chain of Cycles Skinny. In order to incorporate the level-$\ell$ vertices that lie inside $\triangle$ into the morph of $\langle \varGamma _a(Q),\varGamma _b(Q)\rangle$, we perform a preliminary morph of $\varGamma _a(H')$ to a strictly convex drawing $\varGamma _a^s(H')$ of $H'$ that is skinny, in the sense that it satisfies the following requirements with respect to the disk D and the angle $\phi$ associated with the base edge (u, v) derived from the morph of $\langle \varGamma _a(Q),\varGamma _b(Q) \rangle$ (see also Fig. 4 for an illustration).

• R.1 Every cycle of $\mathcal C$ is drawn inside the disk D.

• R.2 Every cycle of $\mathcal C$ is drawn strictly convex.

• R.3 The cutvertices of $\mathcal C$, as well as d and $d'$, lie on the radius r of D.

• R.4 For every cycle of $\mathcal C$ and for every segment on its boundary, the smaller of the two angles formed at the intersection of the line through r and the line through the segment is smaller than $\phi$.

Fig. 4.

Illustration of the requirements R.1–R.4 of a skinny drawing.

The existence of such a drawing is proven in the following lemma by means of a construction that exploits the properties of $\mathcal C$ given in Lemma 2.

Lemma 3

There exists a drawing $\varGamma _a^s(H')$ of $H'$ that is strictly convex, skinny, and topologically equivalent to $\varGamma _a(H')$.

Proof

We prove the statement by construction. Initially, we place u and v in the same positions as they are in $\varGamma _a(H')$. Further, we place the cutvertices of the chain of cycles $\mathcal C$ as well as d and $d'$ on the radius r in the order they appear in the chain to satisfy R.3. For each cycle c of $\mathcal C$, we proceed as follows. Let x and y be the two vertices of c that have already been placed on r. Let $T^u_{c}$ and $T^v_{c}$ be two isosceles triangles sharing the same base $\overline{xy}$, such that the third vertex of each of them lies inside D and on opposite sides of r and such that the internal angles at x and at y are smaller than $\phi$; refer to the colored triangles in Fig. 4. We place the vertices of c that are incident only to u (only to v) equidistant along a circular arc connecting x and y that lies completely inside $T^u_{c}$ (inside $T^v_{c}$, respectively). By the definition of $T^u_{c}$ and $T^v_{c}$, and also by the fact that the two circular arcs are drawn completely inside $T^u_{c}$ and $T^v_{c}$, it follows that R.1, R.2, and R.4 are satisfied for the drawing of c.

To complete the drawing of $\varGamma _a^s(H')$, we describe how to draw the subgraph $H'_c$ of $H'$ that is contained inside or on the boundary of c such that every internal face of $H'_c$ is strictly convex. Since $H'_c$ is drawn convex in $\varGamma _a(H')$, it admits a strictly convex drawing for any given strictly convex drawing of its outer face [18]. Thus, we can apply the algorithm in [18] to construct a strictly convex drawing of $H'_c$, whose outerface is the drawing of c satisfying R.1-R.4. Finally, we add the edges incident to u and v that are contained inside $\triangle$ to the resulting drawing, which does not introduce crossings due to R.4. This completes the construction of $\varGamma _a^s(H')$. Since every cycle in $\mathcal C$ satisfies R.1–R.4 and since by Observation 1 all faces incident to u and v in $H'$ are triangular, the drawing $\varGamma _a^s(H')$ is strictly convex and skinny as desired. Since our construction and the algorithm in [18] maintain the cyclic order of the edges around each vertex, we have that $\varGamma _a^s(H')$ is topologically equivalent to $\varGamma _a(H')$. This concludes the proof.    $\square$

To describe the morph between $\varGamma _a(H')$ and $\varGamma _a^s(H')$, we need some more work. Since both drawings are strictly convex and topologically equivalent, the preconditions of Theorem 3 are met. However, to ensure that this morph can be done independently for each piece of a kite, we further need to guarantee that vertices u and v do not move and that all vertices of $H'$ remain inside $\triangle$ throughout the morph. As stated in Theorem 3, this can be achieved if the (triangular) outer face is drawn the same in the two input drawings, which is not necessarily the case for $\varGamma _a( H')$ and $\varGamma _a^s(H')$ because of the position of d (recall that u and v have the same position in $\varGamma _a(H')$ and $\varGamma _a^s(H')$). To this end, we augment $\varGamma _a(H')$ and $\varGamma _a^s(H')$ by adding a new vertex $d^*$ in the outer face of $H'$ and connect it to u, v, and d. Moreover, we place $d^*$ at the same position inside $\triangle$ in both $\varGamma _a(H')$ and $\varGamma _a^s(H')$ so that the triangle formed by u, v, and $d^*$ contains all the other vertices of $H'$ (in particular, d). The edge $(d,d^*)$ can always be drawn without crossings, as u, v, and d were the vertices on the outer face of $H'$ before. After this augmentation, we apply Theorem 3 to compute the desired morph of $\langle \varGamma _a(H'),\varGamma _a^s(H') \rangle$, and then we remove $d^*$ from the drawings.

Performing the Global Morph. Applying the above procedure for each piece of a kite yields a drawing $\varGamma _a(G')$ of the supergraph $G'$ of G that is the union of Q and all the graphs $H_\triangle '$ corresponding to every piece of a kite $\triangle$. Observe that $\varGamma _a(G')$ is composed of $\varGamma _a(Q)$ and the skinny drawing $\varGamma ^s_a(H_\triangle ')$ of every graph $H_\triangle '$. To perform the global morph, recall that the vertices of the subgraph Q of $G'$ follow the same trajectories as in the morph between $\varGamma _a(Q)$ and $\varGamma _b(Q)$ (which has been recursively computed). The level-$\ell$ vertices of each subgraph $H_\triangle '$ are moved inside $\triangle$, which again ensures that this can be done independently for each piece of a kite. In the following we describe the trajectories of one such subgraph. We denote this subgraph as $H'$ and adopt the same notation as before.

Since the trajectories of u and v are specified by the morph between $\varGamma _a(Q)$ and $\varGamma _b(Q)$, we only describe the trajectories of $H' \setminus \{u,v\}$, i.e., the vertices of level $\ell$; see Fig. 5 for an example. The drawing of $H' \setminus \{u,v\}$ is a copy of $\varGamma _a^s(H' \setminus \{u,v\})$ rotated and translated so that the cutvertices of $\mathcal C$ as well as d and $d'$ lie on the radius of D perpendicular to (u, v), and the distance between w and $d'$ is the same as in $\varGamma _a^s(H')$. This ensures that the drawing of $H'$ remains skinny, planar (by R.4), and strictly convex at every time instant.

Fig. 5.

Computing the trajectories for the vertices of $H'\setminus \{u,v\}$ based on the, already computed, trajectories of u and v.

Let $\varGamma _b(G')$ be the drawing of $G'$ obtained so far. The next step of the morph is to transform, for each subgraph $H_\triangle '$, the current skinny drawing $\varGamma _b^s(H_\triangle ')$ in $\varGamma _b(G')$ to $\varGamma _b(H_\triangle ')$. By construction, $\varGamma _b^s(H_\triangle ')$ and $\varGamma _b(H_\triangle ')$ are topologically equivalent and strictly convex. Similarly as for $\varGamma _a(H_\triangle ')$, we insert vertex $d^*$ so that the outer face of $H_\triangle '$ is drawn the same in both $\varGamma ^s_b(H'_\triangle )$ and $\varGamma _b(H'_\triangle )$, which allows to apply Theorem 3 independently for each $H_\triangle '$. The target drawing $\varGamma _b(G)$ is obtained by removing the vertices and edges in $G' \setminus G$ and by reinserting the crossed edges in the marked faces. This concludes the proof of Theorem 1.

6 Implications of Theorem 1

In this section, we discuss the applicability of Theorem 1 by presenting meaningful families of 1-planar graphs that admit $1$-kite-planar drawings.

An n-vertex 1-planar graph has at most $4n-8$ edges [13], and if it achieves exactly this density, then it is called optimal. Moreover, any 1-planar drawing of an optimal 1-planar graph G is such that the uncrossed edges induce a plane triconnected quadrangulation P, while each pair of crossing edges of G is drawn inside a corresponding face of P [33]. When restricting to straight-line drawable 1-planar graphs, this bound is reduced to $4n-9$ [21]. Similarly to the general case, an optimal 1-planar straight-line drawing is one in which the uncrossed edges induce a plane triconnected graph whose every inner face is a quadrangle, while the outer face is a triangle [21]. As a consequence, we obtain that each kite is empty and its kite edges are present and uncrossed. Therefore, any optimal 1-planar straight-line drawing is $1$-kite-planar.

Another family of 1-planar graphs that recently attracted considerable attention is the one of IC-planar graphs [3, 15, 19, 30], which admit 1-planar drawings where the crossed edges induce a matching. Note that both the binding edges and the kite edges that are part of an IC-planar drawing are uncrossed. It follows that, if an IC-planar drawing is kite-augmented [14], i.e., it contains all kite edges, then it is $1$-kite-planar. Observe that kite-augmented graphs are also known as locally maximal [24]. Overall, the following result is a corollary of Theorem 1.

Corollary 1

There exists a morph between any pair of topologically-equivalent optimal 1-planar or kite-augmented IC-planar straight-line drawings.

We conclude this section with a remark. As already mentioned, Chambers et al. [17] studied morphs of toroidal graphs and asked to generalize their result to surfaces of higher genus. We note that, since an n-vertex graph embeddable on a surface of genus g has at most $3n+6(g-1)$ edges, while n-vertex optimal 1-planar straight-line drawable graphs have $4n-9$ edges, it follows that the latter do not admit an embedding (without edge crossings) on any surface of bounded genus. Thus, a solution to the open problem by Chambers et al. would not provide morphs of $1$-kite-planar drawings.

7 Open Problems

We made a first step towards the problem of morphing pairs of non-planar drawings. Besides the general open problem of morphing any two such drawings [5], the main questions that stem from our research are as follows: (i) Is it possible to compute morphs of $1$-kite-planar drawings where the vertex trajectories have bounded complexity? (ii) Regardless of the complexity, can we drop P.2 or P.3 of Definition 1? Observe that dropping both would extend Theorem 1 to all 1-planar drawings. (iii) On the other hand, as a relaxation of P.1, further families of beyond-planar graphs [23] could be considered, for instance, does every pair of RAC drawings [22] admit a morph?