11institutetext: Institut für Informatik, Universität Würzburg, Würzburg,
Germany 11email<EMAIL_ADDRESS>
# Morphing Graph Drawings in the Presence of Point Obstacles

Oksana Firman 11 0000-0002-9450-7640 Tim Hegemann 11 0009-0008-4770-3391 Boris
Klemz 11 0000-0002-4532-3765 Felix Klesen 11 0000-0003-1136-5673 Marie Diana
Sieper 11 0009-0003-7491-2811 Alexander Wolff 11 0000-0001-5872-718X Johannes
Zink 11 0000-0002-7398-718X

###### Abstract

A crossing-free morph is a continuous deformation between two graph drawings
that preserves straight-line pairwise noncrossing edges. Motivated by
applications in 3D morphing problems, we initiate the study of morphing graph
drawings in the plane in the presence of stationary point obstacles, which
need to be avoided throughout the deformation. As our main result, we prove
that it is NP-hard to decide whether such an obstacle-avoiding 2D morph
between two given drawings of the same graph exists. This is in sharp contrast
to the classical case without obstacles, where there is an efficiently
verifiable (necessary and sufficient) criterion for the existence of a morph.

###### Keywords:

Graph morphing Point obstacles NP-hard Planar graph

##  1 Introduction

In the field of Graph Drawing, a (crossing-free) morph between two straight-
line drawings $\Gamma_{1}$ and $\Gamma_{2}$ of the same graph is a continuous
deformation that transforms $\Gamma_{1}$ into $\Gamma_{2}$ while preserving
straight-line pairwise noncrossing edges at all times. Morphing (beyond the
above, strict definition in Graph Drawing) has applications in animation and
computer graphics [10]. In this paper, we initiate the study of morphing graph
drawings in the presence of stationary point obstacles, which need to be
avoided throughout the motion.

### Related work.

An obvious necessary condition for the existence of a crossing-free morph in
$\mathbb{R}^{2}$ between two straight-line drawings $\Gamma_{1}$ and
$\Gamma_{2}$ is that these drawings represent the same plane graph (i.e., a
planar graph equipped with fixed combinatorial embedding and a distinguished
outer face). It has been established long ago [7, 14] that this (efficiently
verifiable) criterion is also sufficient, i.e., a crossing-free morph in
$\mathbb{R}^{2}$ between two straight-line drawings of the same plane graph
always exists.

More recent work [2, 12] focuses on efficient computation of such morphs. In
particular, this involves producing a discrete description of the continuous
motion. Typically, this is done in form of so-called piecewise linear morphs.
In a linear morph, each vertex moves along a straight-line segment at a
constant speed (which depends on the length of the segment) such that it
arrives at its final destination at the end of the morph. The (unique) linear
morph between $\Gamma_{1}$ and $\Gamma_{2}$ is denoted by
$\langle\Gamma_{1},\Gamma_{2}\rangle$. A piecewise linear morph is created by
concatenating several linear morphs, which are referred to as (morphing)
steps. A piecewise linear morph consisting of $k$ steps can be encoded as a
sequence of $k+1$ drawings. Alamdari et al. [2] showed that two straight-line
drawings of the same $n$-vertex plane graph always admit a crossing-free
piecewise linear morph in $\mathbb{R}^{2}$ with $O(n)$ steps, which is best-
possible. Their proof is constructive and corresponds to an $O(n^{3})$-time
algorithm, which was later sped up to $O(n^{2}\log n)$ time by Klemz [12].

Other works are concerned with finding crossing-free morphs in
$\mathbb{R}^{2}$ between two given drawings while preserving certain
additional properties, such as convexity [3], upward-planarity [9], or edge
lengths111In the fixed edge length scenario, the drawings are also known as
linkages. [8], or with constructing crossing-free morphs in $\mathbb{R}^{2}$
that transform a given drawing to achieve certain properties, such as vertex
visibilities [1] or convexity [11], while being in some sense monotonic, in
order to preserve the so-called “mental map” [13] of the viewer.

Quite recent works [4, 5, 6] are concerned with transforming two drawings
$\Gamma_{1},\Gamma_{2}$ in the plane into each other by means of crossing-free
morphs in the space $\mathbb{R}^{3}$. Such 2D–3D–2D morphs are always possible
[6]—even if $\Gamma_{1}$ and $\Gamma_{2}$ have different combinatorial
embeddings—and they sometimes require fewer morphing steps than morphs that
are restricted to the plane $\mathbb{R}^{2}$ [4, 5]. Due to connections to the
notoriously open Unknot problem, 3D–3D–3D morphs are not well understood and
have, so far, only been considered for trees [4, 5].

### Our model and motivation.

In this paper, we introduce and study a natural variant of the 2-dimensional
morphing problem: given two crossing-free straight-line drawings $\Gamma_{1}$
and $\Gamma_{2}$ as well as a finite set of points $P$ in $\mathbb{R}^{2}$,
called obstacles, construct (or decide whether there exists) a crossing-free
morph in $\mathbb{R}^{2}$ between $\Gamma_{1}$ and $\Gamma_{2}$ that avoids
$P$, i.e., at no point in time throughout the deformation, the drawing is
allowed to intersect any of the obstacles, which remain stationary. In
particular, this problem naturally arises when constructing 2D–3D–2D morphs,
where it is tempting to apply strategies for the classical 2-dimensional case
on a subdrawing induced by the subset of the vertices contained in a plane
$\pi$. Note that every edge between vertices on different sides of $\pi$
intersects $\pi$ in a point, which then acts as an obstacle for the
2-dimensional morph.

### Contribution and organization.

We begin by stating some basic observations and preliminary results in Section
2. In particular, we observe that the necessary and sufficient condition for
the classical case without obstacles is no longer sufficient for our model
(even when interpreting the obstacles as isolated vertices) and we present a
stronger necessary condition (we say that the obstacles need to be
“compatible” with the drawings), which is, however, still not sufficient. In
fact, as our main result, we show that even if our condition is satisfied, it
is NP-hard to decide whether an obstacle-avoiding morph exists (see Section
3):

######  Theorem 1.1 ()

Given a plane graph $G$, a set of obstacles $P$, and two crossing-free
straight-line drawings $\Gamma$ and $\Gamma^{\prime}$ in $\mathbb{R}^{2}$, it
is NP-hard to decide whether there exists an obstacle-avoiding crossing-free
morph in $\mathbb{R}^{2}$ between $\Gamma$ and $\Gamma^{\prime}$. The problem
remains NP-hard when restricted to the case where $G$ is connected, the
drawings $\Gamma$ and $\Gamma^{\prime}$ are identical except for the positions
of four vertices, and the obstacles $P$ are compatible with $\Gamma$ and
$\Gamma^{\prime}$. (These statements hold regardless of whether the morph is
required to be piecewise linear or not.)

The proof of Theorem 1.1 (by reduction from 3-SAT) is somewhat unusual from a
Graph Drawing perspective: given a Boolean formula $\Phi$, we describe the
construction of a set of obstacles $P$ and two (almost identical) drawings
$\Gamma_{1},\Gamma_{2}$ that exist irrespectively of the satisfiability of
$\Phi$, which instead corresponds to the existence of the obstacle-avoiding
morph between the two drawings. In particular, we had to overcome the somewhat
intricate challenge of designing gadgets that behave in a synchronous way. We
conclude by discussing several open questions in Section 4. Claims marked with
a clickable “$\star$” are proved in the appendix.

### Conventions.

In the remainder of the paper, we consider only morphs in the plane
$\mathbb{R}^{2}$. We write “drawing” as a short-hand for “straight-line
drawing in the plane $\mathbb{R}^{2}$” and, similarly, we write “(planar)
morph” rather than “(crossing-free) morph in $\mathbb{R}^{2}$”. For any
positive integer $n$, we define $[n]=\\{1,2,\dots,n\\}$.

##  2 Preliminaries and Basic Observations

Let $\Gamma_{1}$ and $\Gamma_{2}$ be two drawings of the same plane graph $G$,
and let $P$ be a set of obstacles. We say that $\Gamma_{1}$ and$~{}\Gamma_{2}$
are blocked by $P$ if there is no planar morph between $\Gamma_{1}$ and
$\Gamma_{2}$ that avoids $P$. Moreover, $\Gamma_{1}$ and $\Gamma_{2}$ are
blockable if there exists a set of obstacles that blocks them. We start by
observing that cycles are necessary to block drawings.

######  Proposition 1 ($\star$$\star$)

Let $\Gamma_{1}$ and $\Gamma_{2}$ be two drawings of the same plane forest
$F$. Then $\Gamma_{1}$ and $\Gamma_{2}$ are not blockable.

######  Proof (sketch)

We describe how to construct a morph that avoids an arbitrary set of
obstacles. Assume for now that $F$ consists of a single tree, which we root at
an arbitrary vertex $r$. We construct an obstacle-avoiding planar morph from
$\Gamma_{1}$ to a drawing $\Gamma_{1}^{\prime}$ located in a disk that (i) is
centered on the position of $r$ in $\Gamma_{1}$, (ii) contains no obstacles,
and (iii) whose radius is smaller than the distance between any pair of
obstacles. This can be done by “contracting” the tree along its edges in a
bottom-up fashion (i.e., starting from the leaves). We also morph $\Gamma_{2}$
into an analogously defined drawing $\Gamma_{2}^{\prime}$. The drawings
$\Gamma_{1}^{\prime}$ and $\Gamma_{2}^{\prime}$ can now be translated (far
enough) away from the obstacles without intersecting them so that they can be
transformed into each other by means of morphing techniques for the classical
non-obstacle case [7, 14, 2, 12].

If $F$ contains multiple trees, it is easy to augment $\Gamma_{1}$ and
$\Gamma_{2}$ to drawings of the same plane tree by inserting additional
vertices and edges, thus reducing to the case of a single tree.

We now turn our attention to the case when $G$ may contain cycles. Recall that
an obvious necessary condition for the existence of planar morph between two
drawings is that they represent the same plane graph. Interpreting the
obstacles in the set $P$ as (isolated) vertices reveals that a planar morph
between $\Gamma_{1}$ and $\Gamma_{2}$ that avoids $P$ is possible only if each
obstacle $p\in P$ is located in the same face in $\Gamma_{1}$ and
$\Gamma_{2}$. However, as Fig. 1 shows, this condition is not sufficient. We
say that $P$ is compatible with $\Gamma_{1}$ and $\Gamma_{2}$ if there is a
continuous deformation that transforms $\Gamma_{1}$ into $\Gamma_{2}$ while
avoiding $P$ and preserving pairwise noncrossing (not necessarily straight-
line) edges at all times. The compatibility of $P$ with $\Gamma_{1}$ and
$\Gamma_{2}$ is obviously a necessary condition for the existence of a planar
obstacle-avoiding morph. Note that this condition is violated in Fig. 1(b).

(a)

(b)

Figure 1: The two simple closed curves $\Gamma_{1}$ and $\Gamma_{2}$ in (a)
cannot be continuously deformed into each other without passing over one of
the obstacles (crosses) and while preserving simplicity. (The corresponding
continuous deformation of the geodesic joining the two blue internal obstacles
within the closed curve would transform the curve $g_{1}$ into $g_{2}$ while
keeping the endpoints fixed and without passing over the red external
obstacle, which is impossible.) Consequently, the two drawings of a 4-cycle in
(b) are blocked by the set of three obstacles; it is not compatible with the
two drawings.

Compatibility is unfortunately still not sufficient for the existence of
obstacle-avoiding morphs—even if the considered graph is just a cycle. In the
following, we study and discuss this case in more detail. Let $C_{n}$ denote
the simple cycle with $n$ vertices. Let $\Gamma$ and $\Gamma^{\prime}$ be
drawings of a plane $C_{n}$ such that (i) $\Gamma$ and $\Gamma^{\prime}$ are
distinct (as mappings of $C_{n}$ to the plane), but (ii) the closed curves
realizing $\Gamma$ and $\Gamma^{\prime}$ are identical, and (iii) the set of
points of $\mathbb{R}^{2}$ used to represent vertices is the same in $\Gamma$
and $\Gamma^{\prime}$. Note that there exists an offset $o\in[n-1]$ such that,
for every $i\in[n]$, vertex $i$ in $\Gamma$ is at the same location as vertex
$i+o$ (modulo $n$) in $\Gamma^{\prime}$. Therefore, we say that
$\Gamma^{\prime}$ is a shifted version of $\Gamma$. Due to (ii), every set of
obstacles is compatible with $\Gamma$ and $\Gamma^{\prime}$.

######  Proposition 2 ($\star$$\star$)

Let $n\geq 6$ be an even integer. Then there exists a drawing $\Gamma$ of
$C_{n}$ such that, for every shifted version $\Gamma^{\prime}$ of $\Gamma$,
the drawings $\Gamma$ and $\Gamma^{\prime}$ are blockable by seven obstacles
that are compatible with $\Gamma$ and $\Gamma^{\prime}$ (for an illustration,
see Fig. 3).

It is plausible that Proposition 2 can be strengthened: even three obstacles
seem to be sufficient for blocking two shifted drawings of an even-length
cycle (we chose to use seven obstacles to simplify the proof). In contrast,
mainly due to convexity, more obstacles are needed to block shifted drawings
of $C_{3}$.

######  Proposition 3 ($\star$$\star$)

Two drawings $\Gamma_{1}$ and $\Gamma_{2}$ of $C_{3}$ are not blockable by
four obstacles that are compatible with $\Gamma_{1}$ and $\Gamma_{2}$.

######  Proof (sketch)

We perform a case distinction on the number of obstacles that are located in
the interior of the cycle. Here, we only sketch the case with two inner
obstacles $p_{1}=(x_{1},y_{1})$ and $p_{2}=(x_{2},y_{2})$. Assume without loss
of generality that $x_{1}=x_{2}$ and $y_{1}>y_{2}$. There exists an
$\varepsilon>0$ such that the rectangle
$R=[x_{1}-\varepsilon,x_{1}+\varepsilon]\times[y_{2}-\varepsilon,y_{1}+\varepsilon]$
lies in the interiors of $\Gamma_{1}$ and $\Gamma_{2}$ and, hence, does not
contain any of the outer obstacles; see Fig. 11. Then, for any triangle
$\Gamma\in\\{\Gamma_{1},\Gamma_{2}\\}$, there is a planar morph that moves the
vertices of $\Gamma$ onto the boundary of $R$ while avoiding the line segment
$\overline{p_{1}p_{2}}$ and the region exterior to $\Gamma$. Finally, we show
that two triangles with these properties can always be morphed into each other
while staying in the closure of $R$ and avoiding $\overline{p_{1}p_{2}}$.

Our proof for (at most) two inner obstacles does not depend on the number of
outer obstacles, which implies a partially stronger statement.

We have a tight upper bound for the number of obstacles needed to block
drawings of $C_{3}$; see Fig. 3.

Figure 2: A schematic drawing of $C_{n}$ with vertices $v_{1},\dots,v_{n}$
(here $n=14$) that cannot be morphed to a shifted version of it in a planar
way while avoiding the two internal obstacles (blue crosses) and the five
external obstacles (red crosses).

Figure 3: Five obstacles suffice to block shifted versions of $C_{3}$.

######  Proposition 4 ($\star$$\star$)

Let $\Gamma$ be a drawing of $C_{3}$, and let $\Gamma^{\prime}$ be a shifted
version of $\Gamma$. Then $\Gamma$ and $\Gamma^{\prime}$ are blockable by five
obstacles compatible with $\Gamma$ and $\Gamma^{\prime}$.

We now state a sufficient condition for the existence of planar obstacles-
avoiding morphs between shifted drawings of a cycle. We call a degree-2 vertex
in a drawing free if its two incident edges lie on a common line.

######  Proposition 5 ($\star$$\star$)

Let $\Gamma$ be a drawing of $C_{n}$, and let $\Gamma^{\prime}$ be a shifted
version of $\Gamma$. If $\Gamma$ contains a free vertex, then $\Gamma$ and
$\Gamma^{\prime}$ are not blockable by obstacles that are compatible with
$\Gamma$ and $\Gamma^{\prime}$.

Free vertices are helpful in other specific cases as well (in particular, they
play a crucial role in our NP-hardness proof), but their usefulness is limited
in general: their existence is not a sufficient condition for the existence of
obstacle-avoiding morphs even when it comes to plane cycles; see Fig. 4.

Figure 4: Two drawings of $C_{8}$. If the (red) shaded regions are densely
filled with obstacles, the drawing on the left is essentially locked in
place—it cannot be morphed planarly to a substantially different drawing
without intersecting the obstacle regions. In particular, it cannot be morphed
to the drawing on the right, even though this drawing contains two free
vertices (and the obstacles are compatible with the two drawings).

Finally, we observe that two obstacles are not enough to block two drawings
(with which the obstacles are compatible), regardless of the class of the
represented graph.

######  Proposition 6 ($\star$$\star$)

Let $\Gamma_{1}$ and $\Gamma_{2}$ be two drawings of the same plane graph $G$,
and let $P$ be a set of obstacles that are compatible with $\Gamma_{1}$ and
$\Gamma_{2}$. If $|P|\leq 2$, then there exists a planar morph from
$\Gamma_{1}$ to $\Gamma_{2}$ that avoids $P$.

######  Proof (sketch)

We interpret the (up to) two obstacles as isolated vertices of our plane graph
(by compatibility, each obstacle belongs to the same face in $\Gamma_{1}$ and
$\Gamma_{2}$). By known results [7, 14, 2, 12], there is a morph $M$ in which
$\Gamma_{1}$ is deformed to $\Gamma_{2}$ without introducing crossings and
without intersecting the obstacles. However, since the obstacles are treated
as vertices, their positions might change over time. We can transform $M$ into
the desired morph by translating, rotating, and scaling the frame of reference
as time goes on to ensure that the obstacles become fixpoints (one can think
of this as moving, rotating, and zooming the camera in a suitable fashion).

In view of the remark after Proposition 2, it seems that Proposition 6 is
best-possible. In particular, the proof strategy does not generalize to three
obstacles as affine transformations preserve the cyclic orientations of point
triples.

##  3 Proof of Theorem 1.1

In this section, we show our main result.

See 1.1

###### Proof

We reduce from the classical NP-hard problem 3-SAT. Given a Boolean formula
$\Phi=\bigwedge_{i=1}^{m}c_{i}$ in conjuctive normal form over variables
$x_{1},x_{2},\dots,x_{n}$ whose clauses $c_{1},c_{2},\dots,c_{m}$ consist of
three literals each, we construct a plane graph $G$, two planar drawings
$\Gamma$ and $\Gamma^{\prime}$ of $G$, and a set $P$ of obstacles that are
compatible with $\Gamma$ and $\Gamma^{\prime}$. We show that there exists an
obstacle-avoiding planar morph from $\Gamma$ to $\Gamma^{\prime}$ if and only
if $\Phi$ is satisfiable.

Figure 5: General grid structure used in our NP-hardness reduction. Here, we
use the formula $\Phi=c_{1}\land c_{2}\land c_{3}$, where
$c_{1}=(\ell_{1}^{1}\lor\ell_{1}^{2}\lor\ell_{1}^{3})=(x_{2}\lor x_{1}\lor\neg
x_{3})$, $c_{2}=(\ell_{2}^{1}\lor\ell_{2}^{2}\lor\ell_{2}^{3})=(\neg x_{1}\lor
x_{3}\lor x_{2})$, and
$c_{3}=(\ell_{3}^{1}\lor\ell_{3}^{2}\lor\ell_{3}^{3})=(\neg x_{3}\lor\neg
x_{2}\lor\neg x_{1})$. There are variable gadgets (left), clause and literal
gadgets (top), split gadgets (S), crossing gadgets (C), and a synchronization
gadget (sync) spanning over all clause gadgets. The gadgets have various
states and orientations; dependencies are marked by blue arrows.

### Overview.

In our reduction, we arrange obstacles, vertices, and edges such that we
obtain a grid-like structure where we have two rows for each variable (one for
each literal of the variable) and three columns for every clause (one for each
literal in the clause); see Fig. 5. We then use several gadgets arranged
within this grid-like structure. On the left side, the two rows of a variable
terminate at a variable gadget. A variable gadget is in one of the states
true, false, or unset. On the top side, the three columns of a clause are
connected via three literal gadgets to a clause gadget. Each literal gadget
and each clause gadget is in one of the states true or false. All clause
gadgets are connected by a synchronization gadget. Within the column of each
literal, we have a split gadget in one of the two rows of the corresponding
variable $x_{i}$ – in the upper row if the literal is $x_{i}$ and in the lower
row if the literal is $\lnot x_{i}$. In all other grid cells, we have crossing
gadgets. Every split gadget and every crossing gadget has a horizontal
orientation (left/right) and a vertical orientation (bottom/top).

We first describe the general mechanism of our reduction. Independently of
each other, every variable gadget can be morphed to reach any of its three
states. In $\Gamma$ and $\Gamma^{\prime}$, all crossing and split gadgets have
the orientations left and bottom. A crossing or split gadget $\alpha$ can have
orientation right only if the crossing/split gadget to the left of $\alpha$
has orientation right, too, or if $\alpha$ is adjacent to a variable gadget
with state true (false) and $\alpha$ is in the upper (lower) row of the
corresponding variable. Moreover, a crossing gadget can have orientation top
only if the neighboring crossing/split gadget below has orientation top, too,
and a split gadget can have orientation top only if it can also have
orientation right. A literal gadget can be in the state true only if the
gadget below it has orientation top. A clause gadget is in the state true if
and only if at least one of its three literal gadgets is in the state true.
Moreover, we can reach the final drawing $\Gamma^{\prime}$, where only the
synchronization gadget differs from its drawing in $\Gamma$, if and only if
all clause gadgets have state true simultaneously at some point in time. This
ensures the correctness of our construction.

We now describe and visualize the geometric realization of our gadgets.

### Forbidden areas.

In each gadget, we have forbidden areas where the vertices and edges cannot be
drawn (henceforth drawn solid red). They are used to create a system of
tunnels and cavities in which the edges of our drawings are placed and move;
see, e.g., Fig. 6. We achieve this by densely filling the forbidden areas with
obstacles, which are placed on a fine grid (as explained in more detail in the
paragraph “Number and placement of obstacles” on page 3).

Figure 6: Full construction for the instance $\Phi=(x_{2}\lor x_{1}\lor\neg
x_{3})\land(\neg x_{1}\lor x_{3}\lor x_{2})\land(\neg x_{3}\lor\neg
x_{2}\lor\neg x_{1})$. Gadgets with orientation right/top/true use thicker
strokes.

### Variable gadget.

The variable gadget has a comparatively simple structure; see the three red
boxes on the left side of Fig. 6. It has three vertices enclosed in a straight
vertical tunnel of the forbidden area with one exit on the top right and one
exit on the bottom right. As it is a straight tunnel, the middle vertex, which
we call decision vertex, is a free (see Section 2 for the definition) vertex
(see the thick blue–white vertex of $x_{3}$ in Fig. 6 for the arrangement in
$\Gamma$ and $\Gamma^{\prime}$). We say that the variable gadget is in the
state true (false) if this decision vertex is moved to the top (bottom)
position, and it is in the state unset otherwise. Consequently, we can move
the top (bottom) vertex out of the tunnel if and only if we are in the state
true (false). This, in turn, yields a free vertex for the adjacent row of
crossing and split gadgets, which we describe next.

(a) Base state with horizontal and vertical orientation left and bottom.

(b) If the gadget on the left has horizontal orientation right, vertices can
be pushed one position further and we can reach the orientations right and
top.

Figure 7: Split gadget: from a horizontal row transporting a truth value, we
“copy” the same truth value up to a vertical column.

### Split gadget.

A split gadget consists of a central vertex $c$ of degree 3 together with
paths to the left, right, and top; see Fig. 7. They are enclosed in a system
of tunnels formed by the forbidden area. Fig. 7(a) shows a split gadget
$\sigma$ in the base state as it appears in $\Gamma$ and $\Gamma^{\prime}$. If
the crossing/split/variable gadget to the left of $\sigma$, which shares the
vertex $l$ with $\sigma$, has a free222Here, this means that it is a
crossing/split gadget that is oriented to the right or it is a variable gadget
in its top row with state true or in its bottom row with state false. vertex,
then $l$ can be moved to the next corner of the tunnel. Then, in turn, $c$ can
be moved to the bottom right corner of the white (obstacle-free) triangle in
$\sigma$ (see Fig. 7(b)), and the two other neighbors of $c$ can be pushed one
position to the right and one position up. In this case we say that the
horizontal (vertical) orientation of $\sigma$ is right (top). Otherwise, the
horizontal (vertical) orientation of $\sigma$ is left (bottom).

(a) left \+ bottom

(b) right \+ bottom

(c) left \+ top

(d) right \+ top

Figure 8: Crossing gadget: we transport truth values horizontally and
vertically without influencing each other. The four possible combinations of
orientations are illustrated.

### Crossing gadget.

A crossing gadget has a similar structure as a split gadget. However, we now
have a central vertex $c^{\prime}$ of degree 4 with paths to the neighboring
gadgets to the left, right, top, and bottom. In the center of the crossing
gadget $\chi$ in Fig. 8, there is a white (obstacle-free) square. In $\Gamma$
and $\Gamma^{\prime}$, $c^{\prime}$ is placed in the top left corner of this
square (see Fig. 8(a)). This is the base state of $\chi$. If the gadget on the
left of $\chi$ has a free vertex, we can push the adjacent vertices to the
next corners of the tunnel such that $c^{\prime}$ can move to the bottom side
of the square (see Figs. 8(b) and 8(d)). Only then, we can push the vertices
of the path leaving the gadget on the right side to the next corner of the
tunnel. In this case we say that the horizontal orientation of the crossing
gadget is right; otherwise it is left. Symmetrically, if the gadget below
$\chi$ has a free vertex, we can move $c^{\prime}$ to the right side of the
square (see Figs. 8(c) and 8(d)). Only then we can push the vertices of the
path leaving $\chi$ through the top side to the next corner of the tunnel. In
this case we say that the vertical orientation of the crossing gadget is top;
otherwise it is bottom. Observe that the states of the gadgets on the left and
below $\chi$ independently determine the horizontal and vertical orientation
of $\chi$. This property assures that we can transport information along
routes that cross each other, but do not influence each other.

(a) State false where vertex $t$ is above the forbidden area of the gadget.
This is also the base situation appearing in $\Gamma$ and $\Gamma^{\prime}$.

(b) State true where vertex $t$ is inside the cavity formed by the forbidden
area of the gadget. This state can only be reached if the split or crossing
gadget below has orientation top.

Figure 9: Literal gadget: Depending on the crossing or split gadget below, it
can be in two different states. Only in the state true, vertex $t$ does not
pop out of the gadget.

### Literal gadget.

Fig. 9 shows a literal gadget $\lambda$ in its base state. It consists of five
vertices, one of which, $r$, is shared with the gadget $\beta$ below; see Fig.
9. Only if the vertical orientation of $\beta$ is top, vertex $r$ can move to
the original position of $s$ and $s$ can move up. This in turn allows vertex
$t$ to move into the interior of $\lambda$. In this case, we say that
$\lambda$ has the state true; otherwise it has the state false. If a cycle in
$\Gamma$ contains obstacles, we call the cycle an anchor. Observe that the
anchor $\langle t,w,y\rangle$ restricts the area where we can move $t$.

(a) The clause gadget is in the state false.

(b) The clause gadget is in the state true.

Figure 10: Clause gadget together with three literal gadgets: If at least one
of the literal gadgets is in the state true, the clause gadget is also in the
state true. The obstacle-free region shared with the synchronization gadget is
depicted in hatched green.

### Clause gadget.

Each clause $c_{i}$ ($i\in[m]$) is represented by a clause gadget, which
consists of a path of length 9 whose endpoints are anchored by two 3-cycles;
see Fig. 10. In the base situation occurring in $\Gamma$ and
$\Gamma^{\prime}$, we have exactly one free vertex (denoted by $y$), which is
at the bottom of a large rectangular obstacle-free region, which is also part
of the synchronization gadget. Observe that, within this area, we cannot move
$y$ (up to a tiny bit) to the left or right due to its neighbors lying at
(essentially) fixed positions (see Fig. 10(a)).

However, if one of the incident literal gadgets is in the state true, we get a
second free vertex, due to which we can move $z$, which is a neighbor of $y$,
onto the base position of $y$ (see Fig. 10(b)). Now we can move $y$
arbitrarily far to the right within this obstacle-free region (unless $y$ is
blocked by the edges of another clause gadget). Only when this is done for all
clause gadgets simultaneously, the synchronization gadget (see below) can be
morphed as desired. Thus, we say that a clause gadget is in the state true if
at least one of its literal gadgets is in the state true; otherwise it is in
the state false.

### Synchronization gadget.

The synchronization gadget is a 4-cycle $\langle
v_{1},v_{2},v_{3},v_{4}\rangle$; see Fig. 6. In the base situation occurring
in $\Gamma$, this cycle is drawn as an isosceles trapezoid $T$. In
$\Gamma^{\prime}$, the 4-cycle is drawn as a shifted version (see Section 2
for the definition) of $T$. All sides of $T$ except for the short parallel
side are fixed by tunnels of the forbidden area. In particular, $v_{1}$ and
$v_{4}$ can only be moved in an $\varepsilon$-region (for some small
$\varepsilon>0$) around their initial position, while $v_{2}$ and $v_{3}$ can
potentially be moved to the right into the large obstacle-free rectangular
area (that is shared with all clause gadgets) within a small corridor (see the
blue strips in Fig. 6). These corridors extend the legs of $T$, which have a
specific angle depending on the number of clauses $m$ such that the corridors
intersect at a region $I$ to the right side of all clause gadgets. Note that
we cannot simply “rotate” $T$, since each of the $\varepsilon$-regions around
the positions of $v_{1}$ and $v_{4}$ in $\Gamma$ need to contain at least one
vertex at any time. To reach a shifted version, there needs to be an
intermediate drawing that has a third vertex within the tunnel between these
$\varepsilon$-regions. Therefore, only one vertex remains to close the 4-cycle
on the right side. That vertex needs to be placed inside $I$. Hence, we can
reach the shifted version if and only if all of the clause gadgets are in the
state true: in this case, for each clause gadget, we can move its vertex $y$
into $I$ so that the edges incident to $y$ do not intersect the triangle
$\triangle v_{1}I_{\mathrm{left}}v_{4}$, where $I_{\mathrm{left}}$ is the
leftmost point of $I$. Thus, we can place $v_{2}$ onto $I_{\mathrm{left}}$ to
make $v_{3}$ a free vertex and, therefore, reach the shifted drawing of the
4-cycle (cf. Proposition 5). In contrast, if a clause gadget is in the state
false, at least one of the edges incident to its vertex $y$ intersects
$\triangle v_{1}I_{\mathrm{left}}v_{4}$ and, thus, $v_{2}$ and $v_{3}$ cannot
reach the corridors of each other.

### Correctness.

In summary, if $\Phi$ admits a satisfying truth assignment, we can describe a
(piecewise linear) morph from $\Gamma$ to $\Gamma^{\prime}$ by moving the
decision vertices in the variable gadgets according to the truth assignment,
which allows to transport these truth values via the split and crossing
gadgets to the literal and the clause gadgets. As all clause gadgets can reach
the state true at the same time, we can morph the drawing of the 4-cycle in
the synchronization gadget to its shifted version and then move all other
vertices back to their original position.

For the other direction, if a morph from $\Gamma$ to $\Gamma^{\prime}$ exists,
then we know by our construction that at some point, all clause gadgets were
in the state true simultaneously (as this is necessary to morph the drawing of
the 4-cycle in the synchronization gadget to its shifted version), which means
the variable gadgets represent at the same time a satisfying truth assignment
for $\Phi$.

### Number and placement of obstacles.

While the grid-like arrangement of our gadgets depends on $\Phi$, the design
of the variable/clause/literal/crossing/split gadgets does not. Therefore,
each of these gadgets uses only $O(1)$ obstacles, the overall number of
obstacles then is $O(nm)$, and the encoding of their coordinates requires only
polynomially many bits in total. Similarly, the synchronization gadget also
uses only $O(1)$ obstacles, which, for the most part, can be placed on the
grid that is also used by the remaining gadget types. As an exception, two
obstacles (in the top-right and bottom-right corner of the obstacles area
interior to the 4-cycle) need to be placed on a refined grid to ensure that
the area $I$ lies to the right of all clause gadgets. Since vertices $v_{1}$
and $v_{2}$ have constant (horizontal) distance, we use an obstacle that lies
$O(1/m)$ units below the highest possible position of $v_{1}$ and on the same
x-coordinate as $v_{2}$ in $\Gamma$ in order to bound the slope of the
$v_{1}v_{2}$-tunnel from below. We bound the slope of the $v_{3}v_{4}$-tunnel
symmetrically from above. As a result, the area $I$ lies $\Omega(m)$ units to
the right of the vertical line segment $\overline{v_{2}v_{3}}$. Since the
width of the whole construction is $O(m)$, this suffices.

Thus, the encoding of the coordinates of the involved obstacles and the
coordinates of the drawing of the 4-cycle requires only polynomially many
bits.

### Connectivity.

So far, the graph in our reduction has $\Omega(m)$ connected components: a
large connected component comprising all variable, split, crossing and literal
gadgets, a connected component for all clause gadgets, as well as another
connected component for the synchronization gadget. We can merge these
components by adding edges without influencing the behavior of our gadgets: We
add the edges $v_{2}y_{1}$, $y_{1}y_{2}$, …, $y_{m-1}y_{m}$ together with a
path from $y_{m}$ to the large connected component of the other gadgets (e.g.,
in Fig. 6 from $y_{3}$ to $q$).

##  4 Open Problems

  1. 1.

In general, the considered decision problem is NP-hard (Theorem 1.1), but it
can be solved efficiently for forests (Proposition 1). Are there other
meaningful graph classes where this is the case? In particular, what about
cycles or triangulations? It is conceivable that the latter case is actually
easier since the placement of obstacles that are compatible with the two given
drawings is quite limited. Regarding cycles, we emphasize that the existence
of a free vertex is not a sufficient condition for the existence of a morph
(cf. Fig. 4).

  2. 2.

Does the problem lie in NP? Is it $\exists\mathbb{R}$-hard?

  3. 3.

Does the problem become easier if there are only constantly many obstacles?

  4. 4.

The drawings $\Gamma$ and $\Gamma^{\prime}$ produced by our reduction are
identical except for the position of four vertices. It seems quite plausible
that our construction can be modified so that only three vertices change
positions. Does the problem become easier when only up to two vertices may
change positions?

  5. 5.

It is easy to observe that if our reduction is applied to a satisfiable
formula $\Phi$ with $n$ variables and $m$ clauses, there is a piecewise linear
obstacle-avoiding morph between the produced drawings $\Gamma$ and
$\Gamma^{\prime}$ with $\Theta(n+m)$ steps, which is also necessary. Note that
this number is not independent from the output size of the reduction. This
motivates the following family of questions. Let $k$ be a fixed arbitrary
constant. Given two planar straight-line drawings $\Gamma$ and
$\Gamma^{\prime}$ of the same plane graph and a set of obstacles compatible
with $\Gamma$ and $\Gamma^{\prime}$, decide whether there exists a piecewise
linear obstacle-avoiding morph from $\Gamma$ to $\Gamma^{\prime}$ with at most
$k$ steps. For which values of $k$ can this decision problem be answered
efficiently?

  6. 6.

Given two drawings of the same plane graph, how many compatible obstacles are
necessary and sufficient to block them? Can this be computed efficiently?

## References

  * [1] O. Aichholzer, G. Aloupis, E. D. Demaine, M. L. Demaine, V. Dujmovic, F. Hurtado, A. Lubiw, G. Rote, A. Schulz, D. L. Souvaine, and A. Winslow.  Convexifying polygons without losing visibilities.  In G. Aloupis and Bremner, editors, CCCG, pages 229–234, 2011.  URL: http://www.cccg.ca/proceedings/2011/papers/paper70.pdf.
  * [2] S. Alamdari, P. Angelini, F. Barrera-Cruz, T. M. Chan, G. Da Lozzo, G. Di Battista, F. Frati, P. Haxell, A. Lubiw, M. Patrignani, V. Roselli, S. Singla, and B. T. Wilkinson.  How to morph planar graph drawings.  SIAM J. Comput., 46(2):824–852, 2017.  doi:10.1137/16M1069171.
  * [3] P. Angelini, G. Da Lozzo, F. Frati, A. Lubiw, M. Patrignani, and V. Roselli.  Optimal morphs of convex drawings.  In L. Arge and J. Pach, editors, SoCG, volume 34 of LIPIcs, pages 126–140. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015.  doi:10.4230/LIPIcs.SOCG.2015.126.
  * [4] E. Arseneva, P. Bose, P. Cano, A. D’Angelo, V. Dujmovic, F. Frati, S. Langerman, and A. Tappini.  Pole dancing: 3D morphs for tree drawings.  J. Graph Algorithms Appl., 23(3):579–602, 2019.  doi:10.7155/jgaa.00503.
  * [5] E. Arseneva, R. Gangopadhyay, and A. Istomina.  Morphing tree drawings in a small 3D grid.  J. Graph Algorithms Appl., 27(4):241–279, 2023.  doi:10.7155/jgaa.00623.
  * [6] K. Buchin, W. S. Evans, F. Frati, I. Kostitsyna, M. Löffler, T. Ophelders, and A. Wolff.  Morphing planar graph drawings through 3D.  In L. Gąsieniec, editor, SOFSEM, volume 13878 of LNCS, pages 80–95. Springer, 2023.  doi:10.1007/978-3-031-23101-8\\_6.
  * [7] S. Cairns.  Deformations of plane rectilinear complexes.  Amer. Math. Monthly, 51(5):247–252, 1944.
  * [8] R. Connelly, E. D. Demaine, and G. Rote.  Straightening polygonal arcs and convexifying polygonal cycles.  Discrete Comput. Geom., 30:205–239, 2003.  doi:10.1007/s00454-003-0006-7.
  * [9] G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, and V. Roselli.  Upward planar morphs.  Algorithmica, 82(10):2985–3017, 2020.  doi:10.1007/s00453-020-00714-6.
  * [10] J. Gomes, L. Darsa, B. Costa, and L. Velho.  Warping & Morphing of Graphical Objects.  Morgan Kaufmann, 1999.
  * [11] L. Kleist, B. Klemz, A. Lubiw, L. Schlipf, F. Staals, and D. Strash.  Convexity-increasing morphs of planar graphs.  Comput. Geom., 84:69–88, 2019.  doi:10.1016/j.comgeo.2019.07.007.
  * [12] B. Klemz.  Convex drawings of hierarchical graphs in linear time, with applications to planar graph morphing.  In P. Mutzel, R. Pagh, and G. Herman, editors, ESA, volume 204 of LIPIcs, pages 57:1–57:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.ESA.2021.57.
  * [13] H. C. Purchase, E. E. Hoggan, and C. Görg.  How important is the “mental map”? – An empirical investigation of a dynamic graph layout algorithm.  In M. Kaufmann and D. Wagner, editors, GD, volume 4372 of LNCS, pages 184–195. Springer, 2006.  doi:10.1007/978-3-540-70904-6\\_19.
  * [14] C. Thomassen.  Deformations of plane graphs.  J. Combin. Theory Ser. B, 34(3):244–257, 1983.  doi:10.1016/0095-8956(83)90038-2.

## Appendix

See 1

###### Proof

We describe how to construct a morph that avoids an arbitrary set of
obstacles. Assume for now that $F$ consist of a single tree $T$, which we root
at an arbitrary vertex $r$. We construct an obstacle-avoiding planar morph
from $\Gamma_{1}$ to a drawing $\Gamma_{1}^{\prime}$ located in a disk that is
centered on the position of $r$ in $\Gamma_{1}$, contains no obstacles, and
whose radius is smaller than the distance $\gamma$ between any pair of
obstacles. This can be done by “contracting” the tree along its edges in a
bottom-up fashion (i.e., starting from the leaves); we discuss this process in
more detail below. We also morph $\Gamma_{2}$ into an analogously defined
drawing $\Gamma_{2}^{\prime}$. The drawings can now be translated (far enough)
away from the obstacles without intersecting them so that they can be
transformed into each other by means of morphing techniques for the classical
non-obstacle case [7, 14, 2, 12].

If $F$ contains multiple trees, it is easy to augment $\Gamma_{1}$ and
$\Gamma_{2}$ to drawings of the same plane tree by inserting additional
vertices and edges, thus, reducing to the case of a single tree.

### Contraction.

It remains to discuss the aforementioned contraction step. To this end, it
suffices to prove the following statement:

Let $v$ be a vertex of $T$ and let $T_{v}$ be the subtree of $T$ rooted at
$v$. Further, let $\Gamma$ be a drawing of $T$ and let $\varepsilon$ be a
positive number such that the disk $D^{v}_{\varepsilon}$ of radius
$\varepsilon$ centered on $v$ contains no obstacle and no vertex other than
$v$ and intersects only edges that are incident to $v$. Then there is a planar
obstacle-avoiding morph from $\Gamma$ to a drawing $\Gamma^{v}$ of $T$ in
which the subdrawing of $T_{v}$ is located in $D^{v}_{\varepsilon}$. Further,
$v$ and all vertices that do not belong to $T_{v}$ are placed exactly as in
$\Gamma$.

Note that, indeed, by chosing $\varepsilon<\gamma$ and $\Gamma=\Gamma_{1}$,
the drawing $\Gamma^{r}$ corresponds to the desired drawing
$\Gamma_{1}^{\prime}$.

We prove the statement by induction on the height of $T_{v}$. If $v$ is a
leaf, the statement follows trivially. So suppose $v$ is not a leaf. Let
$c_{1},c_{2},\dots,c_{k}$ be the children of $v$. For each child $c_{i}$, we
choose a radius $\delta_{i}\ll\varepsilon$ radius such that the disk
$D^{c_{i}}_{\delta_{i}}$ contains no vertex other than $c_{i}$, intersects
only edges incident to $c_{i}$, and can be translated in direction
$\overrightarrow{c_{i}v}$ until it is fully contained in $D^{v}_{\varepsilon}$
without intersecting any obstacles or edges of $\Gamma$ that are not incident
to vertices of $T_{c_{i}}$. Moreover, we choose these radii small enough such
that when carrying out these translations simultaneously, the disks
$D^{c_{i}}_{\delta_{i}}$ do not intersect each other. Clearly, such a set of
radii exists. Now we can inductively contract each subtree $T_{c_{i}}$ into
its disk $D^{c_{i}}_{\delta_{i}}$ and simultaneously apply the described
translations to obtain the desired morph to the drawing $\Gamma^{v}$.

See 2

###### Proof

Let $\Gamma$ be a drawing of $C_{n}$ that it is wrapped around an imaginary
equilateral triangle $\triangle$ formed by the positions of the first three
vertices of $C_{n}$; see Fig. 3. We place $\triangle$ such that its bottom
edge is horizontal. We start with the first vertex $v_{1}$ of $C_{n}$ in the
lower right corner of $\triangle$. Then we go clockwise around $\triangle$. In
step $i$, we place $v_{i+1}$ and $v_{n-i+2}$ near the current corner of
$\triangle$ such that the two new vertices see their predecessors (and will
see their successors) and lie slightly further away from the barycenter of
$\triangle$ than the other vertices that we have placed near the same corner
of $\triangle$. We can place the vertices of $C_{n}$ (and four of the
obstacles, see below) such that each of them lies within a
radius-$\varepsilon$ circle centered at one of the corners of $\triangle$, for
some $\varepsilon>0$. These radius-$\varepsilon$ circles correspond to the
green areas in the schematic drawing in Fig. 3.

We place two obstacles in the interior of $C_{n}$, namely in the immediate
vicinity of $v_{1}$ and $v_{n/2+1}$ (see the blue crosses in Fig. 3).
Additionally, we place five obstacles in the complement of $C_{n}$ (see the
red crosses in Fig. 3). First, we place two of these in the immediate vicinity
of $v_{2}$ and $v_{3}$, slightly closer than those to the barycenter of
$\triangle$. Then, we place the remaining three obstacles very close to the
midpoints of the three outermost edges of $C_{n}$ (that is,
$v_{n/2+2}v_{n/2+3}$, $v_{n/2+3}v_{n/2+4}$, and $v_{n/2+4}v_{n/2+5}$). Due to
the tight wrapping of $C_{n}$ around $\triangle$ and the extra obstacles on
each of the three sides of the drawing, it is impossible to move, for any
$i\in[n]$, vertex $v_{i}$ (except $v_{n/2+1}$) by a distance of more than
$\varepsilon$ without hitting an edge and without its incident edges hitting
an obstacle or another edge. Although we can move $v_{n/2+1}$ (roughly in the
direction away from its neighbors), this does not help us to further unwrap
the drawing. Moreover, no group of vertices can be moved simultaneously.
Hence, $\Gamma$ and $\Gamma^{\prime}$ are blocked for every shifted version
$\Gamma^{\prime}$ of $\Gamma$.

See 3

###### Proof

Due to compatability we know that both drawings have the same (combinatorial)
outer face. We consider five cases depending on the number of internal
obstacles.

### Case 0:

If there is no internal obstacle, a morph cannot be blocked: We can scale both
drawings down with respect to their barycenters and then morph between them as
follows.

Let $P=\\{p_{1},\dots,p_{4}\\}$ be the set of (external) obstacles. Let
$b_{1}$ and $b_{2}$ be the barycenters of $\Gamma_{1}$ and $\Gamma_{2}$,
respectively. Let
$\varepsilon_{1}=\min_{i\in[2],j\in[4]}\\{|b_{i}p_{j}|\\}/3$. We scale both
drawings with respect to their barycenters such that the drawings lie inside
circles $C_{1}$ and $C_{2}$ of radius $\varepsilon_{1}$ centered at $b_{1}$
and $b_{2}$, respectively. Let $\tilde{\Gamma}_{1}$ and $\tilde{\Gamma}_{2}$
be the scaled versions of $\Gamma_{1}$ and $\Gamma_{2}$, respectively. Let
$r=\overline{b_{1}b_{2}}$ be the segment with endpoints $b_{1}$ and $b_{2}$,
and let $r_{1}$ and $r_{2}$ be the two (different) lines parallel to $r$ that
touch circles $C_{1}$ and $C_{2}$. Let $R$ be the region bounded by $r_{1}$,
$r_{2}$, $C_{1}$, and $C_{2}$ that contains $\tilde{\Gamma}_{1}$ and
$\tilde{\Gamma}_{2}$. If $R$ does not contain any obstacle, we can easily
morph $\tilde{\Gamma}_{1}$ to $\tilde{\Gamma}_{2}$ using a constant number of
linear morphing steps. Otherwise we further scale both drawings such that
their joint convex hull is empty. We do this as follows. If $r$ does not
contain any obstacles, we scale $\tilde{\Gamma}_{1}$ and $\tilde{\Gamma}_{2}$
with respect to $b_{1}$ and $b_{2}$, respectively, such that both drawings lie
inside circles of radius
$\varepsilon_{2}=\min_{i\in[2],j\in[4]}\\{|rp_{j}|,|rr_{i}|\\}/3$. If $r$
contains an obstacle, we move $\tilde{\Gamma}_{1}$ and $\tilde{\Gamma}_{2}$
perpendicular to $r$, such that both drawings still lie in the interior of $R$
and the line segment $\tilde{r}$ connecting the new barycenters does not
contain any obstacles. Note that there always exist such a move. Then we scale
the drawings once more as in the previous scaling step, but with respect to
$\tilde{r}$ instead of $r$. Now the resulting triangles lie in a sufficiently
large empty region, hence we can morph between one and the other using a
constant number of linear morphing steps. Note that this idea works even if we
have any number of outer obstacles.

### Case 1:

If there is only one obstacle $p$ in the inner faces of both triangles, the
intersection of the interiors of $\Gamma_{1}$ and $\Gamma_{2}$ is not empty.
Let $C$ be a circle (of positive radius) centered at $p$ and contained in the
intersection of the interiors of $\Gamma_{1}$ and $\Gamma_{2}$. Then we morph
the vertices of both drawings along the segments between the vertices and $p$
until they reach the circle $C$ using a single linear morph. Note that while
morphing we avoid the outer obstacles. Now we “rotate” $\Gamma_{1}$ until one
of it vertices, reaches the corresponding vertex of $\Gamma_{2}$. We implement
this “rotation” stepwise, using a constant number of linear morphs. We need
sufficiently many steps such that $p$ stays in the interior of $\Gamma_{1}$
during each step. Finally, we use another linear morph in order to move the
other two vertices of $\Gamma_{1}$ simultaneously to their positions in
$\Gamma_{2}$.

### Case 2:

If there are two internal obstacles (see Fig. 11 (left)), we roughly argue as
follows. We construct a rectangle $R$ that contains the two internal obstacles
and lies in the interior of both drawings $\Gamma_{1}$ and $\Gamma_{2}$. Then
we morph the two drawings such that their vertices lie on the boundary of $R$.
Finally, we morph between the two drawings within the rectangle.

Figure 11: Case 2 of the proof of Proposition 3: two internal obstacles.

To this end, let $P_{\mathrm{in}}=\\{p_{1},p_{2}\\}$ be the set of internal
obstacles. For $i\in[2]$, let $p_{i}=(x_{i},y_{i})$. Without loss of
generality, assume that both obstacles lie on the same vertical line and that
$p_{1}$ lies above $p_{2}$, that is, $x_{1}=x_{2}$ and $y_{1}>y_{2}$. Then let
$\varepsilon=\min\\{d(P_{\mathrm{in}},\Gamma_{1}),d(P_{\mathrm{in}},\Gamma_{2})\\}$
be the minimum distance between either of the two obstacles and either of the
two drawings. Then, for every $\varepsilon^{\prime}<\varepsilon$, the
rectangle
$R=[x_{1}-\varepsilon^{\prime},x_{1}+\varepsilon^{\prime}]\times[y_{2}-\varepsilon^{\prime},y_{1}+\varepsilon^{\prime}]$
lies in the interiors of $\Gamma_{1}$ and $\Gamma_{2}$.

Now let $\Gamma\in\\{\Gamma_{1},\Gamma_{2}\\}$. We show how to morph from
$\Gamma$ to another drawing $\Gamma^{\prime}$ of $C_{3}$ while avoiding the
obstacles such that all the vertices of $\Gamma^{\prime}$ lie on the boundary
of $R$. We do this in four steps as follows; see Fig. 11. Let
$\ell_{p_{1}p_{2}}$ be the vertical line that contains $p_{1}$ and $p_{2}$.
Furthermore let $\ell^{\prime}_{p_{1}p_{2}}$ and
$\ell^{\prime\prime}_{p_{1}p_{2}}$ be the lines parallel to
$\ell_{p_{1}p_{2}}$ that contain the left and the right boundaries of $R$,
respectively. Let $u,v,w$ be the vertices of $\Gamma$. There is always an edge
that completely lies in one of the closed halfplanes of $\ell_{p_{1}p_{2}}$.
W.l.o.g., assume that $uv$ lies completely in the left closed halfplane of
$\ell_{p_{1}p_{2}}$ and $v$ above and to the right of $u$.

Step 1: Now assume, w.l.o.g., that $u$ lies to the left of
$\ell^{\prime}_{p_{1}p_{2}}$, because $\epsilon^{\prime}$ can be arbitrarily
small. Then move $u$ and $v$ along $uw$ and $vw$, respectively, until $u$ lies
on $\ell^{\prime}_{p_{1}p_{2}}$ and $v$ lies on $\ell_{p_{1}p_{2}}$.

Step 2: Move $v$ along $\ell_{p_{1}p_{2}}$ onto the top boundary of $R$ and
move $u$ to the right to some $\delta<\epsilon^{\prime}$ left of
$\ell_{p_{1}p_{2}}$.

Step 3: Similar to the first step we can now move $u$ and $w$ along $uv$ and
$vw$, respectively, until they lie on the boundary of $R$. (Note that in Step
2 there exists some $\delta$ for every position of $w$, such that this step is
possible.)

Note that all these steps are linear morphs and that every intermediate
drawing is contained completely in the orginal drawing, thus we never cross
any outside obstacle.

After applying these steps to both $\Gamma_{1}$ and $\Gamma_{2}$, we get the
drawings $\Gamma_{1}^{\prime}$ and $\Gamma_{2}^{\prime}$, where all vertices
lie on the boundary of $R$.

Further note that now moving $w$ down into the bottom right corner of $R$ and
then $u$ into the bottom left corner of $R$ reaches a canonical configuration.
We now assume that both $\Gamma_{1}^{\prime}$ and $\Gamma_{2}^{\prime}$ are in
this canonical configuration.

To find a morph between $\Gamma_{1}^{\prime}$ and $\Gamma_{2}^{\prime}$ which
keeps all vertices on the boundary of $R$, we describe a partial rotation
which can be repeated as often as needed.

W.l.o.g. assume that the vertices are in a canonical configuration such that
two vertices $u$ and $w$ are in the two bottom corners and the third vertex
$v$ is on the top boundary straight above $p_{1}$.

Now moving $v$ slightly to the right of $\ell_{p_{1}p_{2}}$ and then $w$ to
the left until it is straight below $p_{2}$ lets $u$ move freely along the
left boundary (the line-segment of $\ell^{\prime}_{p_{1}p_{2}}$. If moved
completely up onto the top left corner, $v$ is in turn free to move to the top
right corner, resulting in a configuration symmetric to the starting
configuration. Hence any other shifted version of the $\Gamma_{1}^{\prime}$
can be reached by repetition, this includes $\Gamma_{2}^{\prime}$.

### Case 3:

The case where the inner face contains three obstacles (and hence the outer
face only one) is more complicated. We will morph both $\Gamma_{1}$ and
$\Gamma_{2}$ to the same triangle $\Gamma$ of a specific shape, which we
explain later, and then show that a morph between $\Gamma$ and any shifted
version $\Gamma$ is not blocked.

Let $p_{0}$ be the outer obstacle, and let $p_{1},p_{2},p_{3}$ be the inner
obstacles. If the inner obstacles lie on the same line, this can be solved in
the same way as case 2.

Thus, w.l.o.g. assume that the x-coordinates of the obstacles are as follows:
$x({p_{0}})<x({p_{1}})=x({p_{2}})<x({p_{3}})$. Let $\ell_{p_{1}p_{2}}$ be a
vertical line that contains both $p_{1}$ and $p_{2}$. Let $\ell_{p_{3}}$ be a
line parallel to $\ell_{p_{1}p_{2}}$ that contains $p_{3}$. Let $r_{p_{i}}$,
for $i=\\{1,2,3\\}$, be a ray that starts in $p_{0}$ and contains $p_{i}$.
Note that one of the rays is inside the wedge made by the other two. W.l.o.g.
assume that $r_{p_{3}}$ is the middle ray. Let $W$ be the wedge made by
$r_{p_{1}}$ and $r_{p_{2}}$.

We create the triangle $\Gamma$ as follows, see Fig. 12(a) (left). Let $a,b,c$
be the vertices of $\Gamma$. We place $a$ in the vicinity of $p_{0}$ inside
$W$. The vertices $b$ and $c$ we place on a vertical line right of
$\ell_{p_{3}}$, such that $b$ is above and $c$ is below the wedge $W$. Note
that $\Gamma$ contains the inner obstacles in its inner face and the outer
obstacle in its outer face.

Now we show step by step how to morph from $\Gamma_{1}$, respectively
$\Gamma_{2}$, to the drawing $\Gamma$ or a shifted version of $\Gamma$ (if the
obstacles are compatible with both drawings); see Fig. 12(a). Note that every
of the following steps can be realized by a linear morph. Let $u,v,w$ be the
vertices of $\Gamma^{\prime}$. Let $\ell_{bc}$ be a vertical line containing
$b$ and $c$.

Step 1: If there is only one vertex of $\Gamma^{\prime}$ right to $\ell_{bc}$,
say $w$, then the edge $uv$ is completely to the left of $\ell_{bc}$
(including the case where one of the vertices lie on $\ell_{bc}$). If the line
that contains $uv$ is vertical, we first rotate the vertices $u$ and $v$ along
the lines containing $uw$ and $vw$, respectively. W.l.o.g. assume that $u$ is
closer to the intersection of lines containing $uv$ and $bc$. We first move
$u$ and then $w$ along the lines containing $uv$ and $vw$, respectively, until
they both are on the line $\ell_{bc}$.

Step 2: We first move $v$ and then $w$ along the lines containing $uv$ and
$bw$, respectively, until they both are on the line containing $ab$. Note that
$w$ will be already coincident with $b$.

Step 3: We move $v$ and $u$ along the lines containing $vw$ and $uw$,
respectively, until they both are on a line containing $ac$. Note that now
$\Gamma^{\prime}$ is coincident with $\Gamma$.

It remains to show that we can morph between $\Gamma$ and any shifted version
of $\Gamma$. We show step by step how we morph from $\Gamma$ to its clockwise
shifted version; see Fig. 12(b). Note that every of the following steps can be
realized by a linear morph. Let $\ell_{ab},\ell_{bc},\ell_{ac}$ be the lines
containing $ab,bc,ac$, respectively, before we do a morph. Let $\ell_{b}$ and
$\ell_{c}$ be lines containing $b$ and $c$, respectively, such that the slope
of $\ell_{b}$ is negative and the slope of $\ell_{c}$ is positive. Thus, the
intersection of $\ell_{b}$ and $\ell_{c}$, denote by $b^{\prime}$, is to the
right of $\ell_{bc}$. Let $a^{\prime}$ be the intersection of $\ell_{ac}$ and
$\ell_{b}$, and let $c^{\prime}$ be the intersection of $\ell_{ab}$ and
$\ell_{c}$.

Step 1: Move $a$ along $\ell_{ac}$ to $a^{\prime}$.

Step 2: Move $b$ along $\ell_{b}$ to $b^{\prime}$.

Step 3: Move $a$ and $c$ along $\ell_{b}$ and $\ell_{c}$, respectively, to the
line $\ell_{ab}$.

Step 4: Move $b$ along $\ell_{c}$ to the line $\ell_{bc}$.

Step 5: Move $c$ along $ca$ to the line $\ell_{ac}$.

Note that in every step there is no crossing with the obstacles. We get the
shifted (clockwise) version of $\Gamma$.

(a) Morph from $\triangle uvw$ to $\triangle abc$.

(b) Morph between $\triangle abc$ and its shifted version.

Figure 12: Case 3 (three obstacles in the inner face and one in the outer
face) in the proof of Proposition 3.

### Case 4:

If all obstacles are internal, we scale both drawings up with respect to the
barycenter of $P$ such that the obstacles behave like a single obstacle.

See 4

###### Proof

We block a morph between $\Gamma$ and $\Gamma^{\prime}$ if we put three
obstacles in the inner face of $\Gamma$ in the vicinity of each vertex, i. e.,
inside a disc with radius $\varepsilon>0$, and the other two obstacles in the
outer face of $\Gamma$ close to two different edges of $\Gamma$, namely, in
the $\varepsilon$-distance to the midpoints of the edges; see Fig. 13.

Figure 13: Five obstacles suffice to block shifted versions of $C_{3}$.

We show by contradiction that the obstacles chosen in this way block a morph
between $\Gamma$ and $\Gamma^{\prime}$.

Let $a$, $b$ and $c$ be the vertices of $C_{3}$. Let
$a^{\prime},b^{\prime},c^{\prime}$ be obstacles in the inner face of $\Gamma$
that are in the vicinity of $a$, $b$, $c$, respectively. Let $a_{b}^{\prime}$
and $a_{c}^{\prime}$ be obstacles in the outer face of $\Gamma$ close to the
edges $ab$ and $ac$, respectively. Furthermore, without loss of generality,
assume that $a$ has the biggest $y$-coordinate in $\Gamma$ and $b$ and $c$ are
on the different sides of the vertical line going through $a$. Let without
loss of generality $\langle a,b,c\rangle$ be the clockwise order of the
vertices of $\Gamma$. Assume that there is a morph from $\Gamma$ to a shifted
version $\Gamma^{\prime}$, such that $c$ is the vertex with the biggest
$y$-coordinate in $\Gamma^{\prime}$. In order for a morph between $\Gamma$ and
$\Gamma^{\prime}$ to exist, there must be an intermediate drawing
$\tilde{\Gamma}$, where $a$ and $c$ lie on the same horizontal line, i.e.,
have the same $y$-coordinate. Clearly, the line has to be above the obstacle
$a^{\prime}$. In order for the edge $ab$ to not cross any of the obstacles,
$b$ has to lie to the right of the line that contains both $b^{\prime}$ and
$a_{b}^{\prime}$ and to the bottom of the line that contains both $a^{\prime}$
and $a_{b}^{\prime}$. On the other hand, in order for $bc$ not to cross any of
the obstacles, symmetrically $b$ has to lie to the left of the line that
contains $c^{\prime}$ and $a_{c}^{\prime}$, and to the bottom of the line that
contain $a^{\prime}$ and $a_{c}^{\prime}$. We assume that we have picked
$\varepsilon$ small enough, such that the slope of the line that contains
$b^{\prime}$ and $a_{b}^{\prime}$ is $<0$, and the slope of the line that
contains $c^{\prime}$ and $a_{c}^{\prime}$ is $>0$. Now the regions where $b$
has to be according to the edge $ab$ and where $b$ has to be according to $ac$
do not overlap. Hence, the intermediate drawing $\tilde{\Gamma}$ cannot exist,
and $\Gamma$ and $\Gamma^{\prime}$ are blocked by the set of obstacles. Thus,
$\Gamma$ and $\Gamma^{\prime}$ are blockable.

See 5

###### Proof

Let $v_{0},v_{1}\dots,v_{n-1}$ be the vertices of $C_{n}$ in clockwise order
around $\Gamma$ such that $v_{0}$ is the free vertex. We move $v_{0}$
immediately next to $v_{1}$ such that $v_{1}$ lies on the line segment
$\overline{v_{0}v_{2}}$. As a result, $v_{1}$ is free. Iterating this move for
every vertex until $v_{0}$ becomes free again yields a morph from $\Gamma$ to
a shifted version $\Gamma_{1}$ of $\Gamma$, where, for every $i\in[n-2]$,
vertex $v_{i}$ has moved to the position of its successor $v_{i+1}$ and vertex
$v_{n-1}$ has moved to the position of $v_{1}$. Repeating the whole procedure
as often as necessary yields a morph from $\Gamma$ to any shifted version of
$\Gamma$.

See 6

###### Proof

We show the statement for a set $P=\\{p_{1},p_{2}\\}$ of size 2. Without loss
of generality, we assume $d(p_{1},p_{2})=1$. Let $G^{\prime}$ be the plane
graph obtained from $G$ by introducing two new isolated vertices $v_{1}$ and
$v_{2}$ and assigning them into the faces where the obstacles $p_{1}$ and
$p_{2}$ lie in $\Gamma_{1}$ (and thus also in $\Gamma_{2}$). Let
$\Gamma^{\prime}_{1}$ and $\Gamma^{\prime}_{2}$ be the drawings of
$G^{\prime}$ that are obtained from $\Gamma_{1}$ and $\Gamma_{2}$,
respectively, by placing $v_{1}$ and $v_{2}$ at the positions of $p_{1}$ and
$p_{2}$, respectively.

We know that there exists a morph $M_{1}$ from $\Gamma^{\prime}_{1}$ to
$\Gamma^{\prime}_{2}$ [7, 14, 2, 12]. We can treat $M_{1}$ as a continuous
function from the interval $[0,1]$ onto the set of straight-line drawings of
$G^{\prime}$ such that $M_{1}(0)=\Gamma^{\prime}_{1}$ and
$M_{1}(1)=\Gamma^{\prime}_{2}$. Since $M_{1}$ is continuous, the function
$t\colon[0,1]\rightarrow\mathbb{R}^{2}$ that describes the position of $v_{1}$
in $\mathbb{R}^{2}$ relative to its starting point during the morph $M_{1}$ is
continuous as well, and since $v_{1}$ is drawn at the same position in
$\Gamma^{\prime}_{1}$ and $\Gamma^{\prime}_{2}$, we know that
$t(0)=t(1)=(0,0)$. We now define a new morph $M_{2}$ that is obtained from
$M_{1}$ by translating $M_{1}(x)$ by the vector $-t(x)$ for every $x\in[0,1]$.
Then $M_{2}$ is a continuous morph from $\Gamma^{\prime}_{1}$ to
$\Gamma^{\prime}_{2}$, and, for every $x\in[0,1]$, in the drawing $M_{2}(x)$,
vertex $v_{1}$ is placed at $p_{1}$.

In the same manner, we define the function
$s\colon[0,1]\rightarrow\mathbb{R}>0$ that describes the distance between
$v_{1}$ and $v_{2}$ in $M_{2}(x)$ for all $x\in[0,1]$. Since
$d(p_{1},p_{2})=1$, we know that $s(0)=s(1)=1$, and $s$ is continuous since
$M_{2}$ is continuous. We define a new morph $M_{3}$ that is obtained from
$M_{2}$ by scaling $M_{2}(x)$ by the factor $1/s(x)$ around the point $v_{1}$
for every $x\in[0,1]$. Then $M_{3}$ is a continuous morph from
$\Gamma^{\prime}_{1}$ to $\Gamma^{\prime}_{2}$, where $v_{1}$ is fixed at the
same position by $M_{3}$, and the distance between $v_{1}$ and $v_{2}$ is
equal to 1 in $M_{3}(x)$ for every $x\in[0,1]$.

We define a third function $r\colon[0,1]\rightarrow\mathbb{R}>0$ that
describes the angle between the horizontal lines going throught $v_{1}$ and
$v_{2}$ in $M_{2}(x)$ and in $\Gamma^{\prime}_{1}$ for all $x\in[0,1]$. Since
$v_{1}$ and $v_{2}$ are in the same position in $\Gamma_{1}^{\prime}$ and
$\Gamma_{2}^{\prime}$, we know that $r(0)=r(1)=0$, and $r$ is continuous since
$M_{3}$ is continuous. We define a new morph $M_{4}$ that is obtained from
$M_{3}$ by rotating $M_{3}(x)$ around $v_{1}$ by an angle of $-r(x)$ for every
$x\in[0,1]$. Then $M_{4}$ is a continuous morph from $\Gamma^{\prime}_{1}$ to
$\Gamma^{\prime}_{2}$, where $v_{1}$ is fixed at the same position by $M_{4}$,
the distance between $v_{1}$ and $v_{2}$ is equal to 1 in $M_{4}(x)$ for every
$x\in[0,1]$, and the line between $v_{1}$ and $v_{2}$ does not change its
angle during the morph. Thus, $v_{2}$ is fixed by $M_{4}$ as well. Then, if we
restrict $M_{4}$ to $G$, we obtain a morph from $\Gamma_{1}$ to $\Gamma_{2}$
that avoids $P$, which proves the statement for $|P|=2$.

The case where $|P|=1$ can be obtained from the case where $|P|=2$ by placing
a second obstacle in the vicinity of the first one.