11institutetext: Institute of Software Technology, Graz University of
Technology, Austria
11email<EMAIL_ADDRESS>22institutetext: Institut für
Informatik, Freie Universität Berlin, Germany
22email<EMAIL_ADDRESS>
# Flipping Plane Spanning Paths ††thanks: This work was initiated at the 2nd
Austrian Computational Geometry Reunion Workshop in Strobl, June 2021. We
thank all participants for fruitful discussions. J. O. is supported by ERC StG
757609. O. A. and R. P. are supported by FWF grant W1230. B. V. is supported
by FWF Project I 3340-N35. K.K. is supported by the German Science Foundation
(DFG) within the research training group ‘Facets of Complexity’ (GRK 2434).
W.M. is partially supported by the German Research Foundation within the
collaborative DACH project _Arrangements and Drawings_ as DFG Project MU
3501/3-1, and by ERC StG 757609.

Oswin Aichholzer 11 Kristin Knorr 22 Wolfgang Mulzer 22
Johannes Obenaus 22 Rosna Paul 11 Birgit Vogtenhuber 11

###### Abstract

Let $S$ be a planar point set in general position, and let $\mathcal{P}(S)$ be
the set of all plane straight-line paths with vertex set $S$. A flip on a path
$P\in\mathcal{P}(S)$ is the operation of replacing an edge $e$ of $P$ with
another edge $f$ on $S$ to obtain a new valid path from $\mathcal{P}(S)$. It
is a long-standing open question whether for every given point set $S$, every
path from $\mathcal{P}(S)$ can be transformed into any other path from
$\mathcal{P}(S)$ by a sequence of flips. To achieve a better understanding of
this question, we show that it is sufficient to prove the statement for plane
spanning paths whose first edge is fixed. Furthermore, we provide positive
answers for special classes of point sets, namely, for wheel sets and
generalized double circles (which include, e.g., double chains and double
circles).

###### Keywords:

flips plane spanning paths generalized double circles

##  1 Introduction

Reconfiguration is a classical and widely studied topic with various
applications in multiple areas. A natural way to provide structure for a
reconfiguration problem is by studying the so-called _flip graph_. For a class
of objects, the flip graph has a vertex for each element and adjacencies are
determined by a local flip operation (we will give the precise definition
shortly). In this paper we are concerned with transforming plane spanning
paths via edge flips.

Let $S$ be a set of $n$ points in the plane in general position (i.e., no
three points are collinear), and let $\mathcal{P}(S)$ be the set of all plane
straight-line spanning paths for $S$, i.e., the set of all paths with vertex
set $S$ whose straight-line embedding on $S$ is crossing-free. A _flip_ on a
path $P\in\mathcal{P}(S)$ is the operation of removing an edge $e$ from $P$
and replacing it with another edge $f$ on $S$ such that the graph $(P\setminus
e)\cup f$ is again a valid path from $\mathcal{P}(S)$ (note that the edges $e$
and $f$ might cross). The _flip graph_ on $\mathcal{P}(S)$ has vertex set
$\mathcal{P}(S)$ and two vertices are adjacent if and only if the
corresponding paths differ by a single flip. The following conjecture will be
the focus of this paper:

######  Conjecture 1 (Akl et al. [2])

For every point set $S$ in general position, the flip graph on
$\mathcal{P}(S)$ is connected.

### Related work.

For further details on reconfiguration problems in general we refer the reader
to the surveys of Nishimura [9] and Bose and Hurtado [3]. Connectivity
properties of flip graphs have been studied extensively in a huge variety of
settings, see, e.g., [5, 6, 7, 8, 10] for results on triangulations, matchings
and trees.

In our setting of plane spanning paths, flips are much more restricted, making
it more difficult to prove a positive answer. Prior to our work only results
for point sets in convex position and very small point sets were known. Akl et
al. [2], who initiated the study of flip connectivity on plane spanning paths,
showed connectedness of the flip graph on $\mathcal{P}(S)$ if $S$ is in convex
position or $|S|\leq 8$. In this convex setting, Chang and Wu [4] derived
tight bounds concerning the diameter of the flip graph, namely, $2n-5$ for
$n=3,4$, and $2n-6$ for $n\geq 5$.

For the remainder of this paper, we consider the flip graph on
$\mathcal{P}(S)$ (or a subset of $\mathcal{P}(S)$). Moreover, unless stated
otherwise, the word _path_ always refers to a path from $\mathcal{P}(S)$ for
an underlying point set $S$ that is clear from the context.

Figure 1:  The three types of flips in plane spanning paths.

### Flips in plane spanning paths.

Let us have a closer look at the different types of possible flips for a path
$P~{}=~{}v_{1},\dots,v_{n}~{}\in~{}\mathcal{P}(S)$ (see also Figure 1). When
removing an edge $v_{i-1}v_{i}$ from $P$ with $2\leq i\leq n$, there are three
possible new edges that can be added in order to obtain a path (where, of
course, not all three choices will necessarily lead to a valid path in
$\mathcal{P}(S)$): $v_{1}v_{i}$, $v_{i-1}v_{n}$, and $v_{1}v_{n}$. A flip of
_Type 1_ is a valid flip that adds the edge $v_{1}v_{i}$ (if $i>2$) or the
edge $v_{i-1}v_{n}$ (if $i<n$). It results in the path
$v_{i-1},\dots,v_{1},v_{i},\dots,v_{n}$, or the path
$v_{1},\dots,v_{i-1},v_{n},\dots,v_{i}$. That is, a Type 1 flip inverts a
contiguous chunk from one of the two ends of the path. A flip of _Type 2_ adds
the edge $v_{1}v_{n}$ and has the additional property that the edges
$v_{i-1}v_{i}$ and $v_{1}v_{n}$ do not cross. In this case, the path $P$
together with the edge $v_{1}v_{n}$ forms a plane cycle. If a Type 2 flip is
possible for one edge $v_{i-1}v_{i}$ of $P$, then it is possible for all edges
of $P$. A Type 2 flip can be simulated by a sequence of Type 1 flips, e.g.,
flip $v_{1}v_{2}$ to $v_{1}v_{n}$, then flip $v_{2}v_{3}$ to $v_{1}v_{2}$,
then $v_{3}v_{4}$ to $v_{2}v_{3}$, etc., until flipping $v_{i-1}v_{i}$ to
$v_{i-2}v_{i-1}$. A flip of _Type 3_ also adds the edge $v_{1}v_{n}$, but now
the edges $v_{1}v_{n}$ and $v_{i-1}v_{i}$ cross. Note that a Type 3 flip is
only possible if the edge $v_{1}v_{n}$ crosses exactly one edge of $P$, and
then the flip is possible only for the edge $v_{i-1}v_{i}$ that is crossed.

### Contribution.

We approach Conjecture 1 from two directions. First, we show that it is
sufficient to prove flip connectivity for paths with a fixed starting edge.
Second, we verify Conjecture 1 for several classes of point sets, namely wheel
sets and generalized double circles (which include, e.g., double chains and
double circles).

Towards the first part, we define, for two distinct points $p,q\in S$, the
following subsets of $\mathcal{P}(S)$: let $\mathcal{P}(S,p)$ be the set of
all plane spanning paths for $S$ that start at $p$, and let
$\mathcal{P}(S,p,q)$ be the set of all plane spanning paths for $S$ that start
at $p$ and continue with $q$. Then for any $S$, the flip graph on
$\mathcal{P}(S,p,q)$ is a subgraph of the flip graph on $\mathcal{P}(S,p)$,
which in turn is a subgraph of the flip graph on $\mathcal{P}(S)$. We
conjecture that all these flip graphs are connected:

###### Conjecture 2

For every point set $S$ in general position and every $p\in S$, the flip graph
on $\mathcal{P}(S,p)$ is connected.

###### Conjecture 3

For every point set $S$ in general position and every $p,q\in S$, the flip
graph on $\mathcal{P}(S,p,q)$ is connected.

Towards Conjecture 1, we show that it suffices to prove Conjecture 3:

######  Theorem 1.1 ()

Conjecture 2 implies Conjecture 1.

######  Theorem 1.2 ()

Conjecture 3 implies Conjecture 2.

Figure 2:  Example where the flip graph is disconnected if the first three
vertices of the paths are fixed. No edge of the solid path can be flipped, but
there is at least one other path (dotted) with the same three starting
vertices.

Note that the analogue of Conjecture 3 for paths where the first $k\geq 3$
vertices are fixed, does not hold: Figure 2 shows a counterexample with $7$
points and $k=3$.

Towards the flip connectivity for special classes of point sets, we consider
wheel sets and generalized double circles. A point set is in _wheel
configuration_ if it has exactly one point inside the convex hull. For
generalized double circles we defer the precise definition to Section 4,
however, intuitively speaking a generalized double circle is obtained by
replacing each edge of the convex hull by a flat enough concave chain of
arbitrary size (as depicted on the right). We show that the flip graph is
connected in both cases:

######  Theorem 1.3 ()

Let $S$ be a set of $n$ points in wheel configuration. Then the flip graph (on
$\mathcal{P}(S)$) is connected with diameter at most $2n-4$.

######  Theorem 1.4 ()

Let $S$ be a set of $n$ points in generalized double circle configuration.
Then the flip graph (on $\mathcal{P}(S)$) is connected with diameter at most
$O(n^{2})$.

Finally, we remark that using the order type database [1], we are able to
computationally verify Conjecture 1 for every set of $n\leq 10$ points in
general position (even when using only Type 1 flips).111The source code is
available at https://github.com/jogo23/flipping_plane_spanning_paths.

### Notation.

We denote the convex hull of a point set $S$ by $\operatorname{CH}(S)$. All
points $p\in S$ on the boundary of $\operatorname{CH}(S)$ are called _extreme
points_ and the remaining points are called _interior_ points.

##  2 A Sufficient Condition

In this section we prove Theorem 1.1 and Theorem 1.2.

######  Lemma 1 ()

Let $S$ be a point set in general position and $p,q\in S$. Then there exists a
path $P\in{\cal P}(S)$ which has $p$ and $q$ as its end vertices.

###### Proof

We consider two different cases. Let us first assume that at least one of the
two points, w.l.o.g. say $p$, is not an extreme point of $S$. Sort all other
points of $S$ radially around $p$, starting at $q$. Connect $p$ to the second
point in this order (the point radially just after $q$) and connect all other
points in radial order to a path, such that $q$ becomes the last point of this
path; see Figure 3 (left). Since $p$ is an interior point, each edge of this
path stays in a cone defined by $p$ and two successive points in the radial
order, in particular all these cones are disjoint. Hence, we have obtained a
plane spanning path starting at $p$ and ending at $q$.

Assume now for the second case that both given points lie on the boundary of
the convex hull of $S$. Then consider two tangents of the convex hull of $S$
going through $p$ and $q$, respectively. By the general position assumption of
$S$ we can always perturb these two tangents so that they still go through the
two given vertices but are not parallel, and thus cross in a point $x$ outside
of the convex hull of $S$; see Figure 3 (right). Sort all points radially
around $x$ and connect the points in this order to a path. By construction the
points $p$ and $q$ are the first and last point in this sorting, and we thus
obtain the required path.∎

Figure 3:  For any two given points $p$ and $q$ there exists a plane spanning
path having these two points as start and target points. Left: the case if at
least one of the two points is in the interior of the point set. Right: the
case when both points are on the boundary of the convex hull.

See 1.1

###### Proof

Let $S$ be a point set and $P_{s},P_{t}\in\mathcal{P}(S)$. If $P_{s}$ and
$P_{t}$ have a common endpoint, we can directly apply Conjecture 2 and the
statement follows. So assume that $P_{s}$ has the endpoints $v_{a}$ and
$v_{b}$, and $P_{t}$ has the endpoints $v_{c}$ and $v_{d}$, which are all
distinct. By Lemma 1 there exists a path $P_{m}$ having the two endpoints
$v_{a}$ and $v_{c}$. By Conjecture 2 there is a flip sequence from $P_{s}$ to
$P_{m}$ with the common endpoint $v_{a}$, and again by Conjecture 2 there is a
further flip sequence from $P_{m}$ to $P_{t}$ with the common endpoint
$v_{c}$. This concludes the proof.∎

Towards Theorem 1.2, we first have a closer look at what edges form _viable_
starting edges. For a given point set $S$ and points $p,q\in S$, we say that
$pq$ forms a _viable_ starting edge if there exists a path
$P\in\mathcal{P}(S)$ that starts with $pq$. For instance, an edge connecting
two extreme points that are not consecutive along $\operatorname{CH}(S)$ is
not a viable starting edge. The following lemma shows that these are the only
non-viable starting edges.

######  Lemma 2 ()

Let $S$ be a point set in general position and $u,v\in S$. The edge $uv$ is a
viable starting edge if and only if one of the following is fulfilled: (i) $u$
or $v$ lie in the interior of $\operatorname{CH}(S)$, or (ii) $u$ and $v$ are
consecutive along $\operatorname{CH}(S)$.

###### Proof

If $u$ and $v$ are extreme points that are not consecutive along
$\operatorname{CH}(S)$, then there exist points to the left and to the right
of the edge $uv$. However, any plane path starting with $uv$ can only reach
the points either to the left or the right.

If $u$ is in the interior of $\operatorname{CH}(S)$, we sort the remaining
points in radial order around $u$. We construct a path starting with $uv$ that
visits the remaining points consecutively in this radial order. We proceed
exactly the same way, if $u$ and $v$ are consecutive extreme points.

If $u$ is an extreme point and $v$ an interior point, let $v_{\ell}$ and
$v_{r}$ be the two neighbors of $u$ along the convex hull. Let
$S^{\prime}\subset S$ be the set of points in the interior of
$\operatorname{CH}(S)$ plus $\\{v_{\ell},v_{r}\\}$. Again we sort the points
of $S^{\prime}$ in radial order around $u$. Let $v^{-}\in S^{\prime}$ be the
vertex that is right before $v$ in this radial order.

We construct three paths $P_{1}=v_{\ell},\ldots,v^{-}$,
$P_{2}=v_{r},\ldots,v$, and $P_{3}=v_{\ell},\ldots,v_{r}$, where $P_{1}$ and
$P_{2}$ simply connect the points in $S^{\prime}$ in radial order (between its
corresponding endpoints). Note that $P_{1}$ may have length zero. $P_{3}$
connects $v_{\ell}$ to $v_{r}$ along the boundary of the convex hull of $S$
(along the side not containing $v_{1}$). Then the union of the three paths
$P_{1},P_{2},P_{3}$ together with $uv$ forms the desired plane spanning path
(see Figure 4 (right)).∎

Figure 4:  _Left:_ $u$ lies inside the convex hull of $S$. _Right:_ $u$ is on
the boundary of the convex hull. For paths $P_{1}$ and $P_{2}$: only vertices
in the radial order around $u$ which are not on the boundary of the convex
hull of $S$, are considered.

The following lemma is the analogue of Lemma 1:

######  Lemma 3 ()

Let $S$ be a point set in general position and $v_{1}\in S$. Further let
$S^{\prime}\subset S$ be the set of all points $p\in S$ such that $v_{1}p$
forms a viable starting edge. Then for two points $q,r\in S^{\prime}$ that are
consecutive in the circular order around $v_{1}$, there exists a plane
spanning cycle containing the edges $v_{1}q$ and $v_{1}r$.

###### Proof

The construction of these plane spanning cycles is completely analogous to the
construction of the paths in the proof of Lemma 2 but we add the proof for the
sake of completeness.

First assume that $v_{1}$ is an interior point. Then, by Lemma 2,
$S^{\prime}=S\setminus\\{v_{1}\\}$ holds. We construct a plane spanning path
starting with $v_{1}q$ and visiting the remaining points in circular order
around $v_{1}$ such that $r$ is the last in this order. Lastly, connect $r$ to
$v_{1}$.

Now, let $v_{1}$ be an extreme point. Again we proceed analogously if $q$ and
$r$ are the two neighbors of $v_{1}$ along $\operatorname{CH}(S)$. Otherwise,
by Lemma 2, at least one of the vertices $q$ or $r$ is an interior point. Then
we construct the same three paths $P_{1},P_{2},P_{3}$ as in Lemma 2 (replacing
the roles of $v,v^{-}$ by $q$ and $r$). Then the union of $P_{1},P_{2},P_{3}$
together with $v_{1}q$ and $v_{1}r$ forms the desired cycle (see Figure 5
(right)).∎

Figure 5:  There exists a plane spanning cycle of $S$ such that $v_{1}$ is
connected to two points neighbored in the radial order around $v_{1}$. _Left:_
$v_{1}$ is an interior point. _Right:_ $v_{1}$ is an extreme point.

We are now ready to prove Theorem 1.2:

See 1.2

###### Proof

Let $S$ be a point set and $v_{1}\in S$. Further let
$P,P^{\prime}\in\mathcal{P}(S,v_{1})$. If $P$ and $P^{\prime}$ have the
starting edge in common, then we directly apply Conjecture 3 and are done. So
let us assume that the starting edge of $P$ is $v_{1}v_{2}$ and the starting
edge of $P^{\prime}$ is $v_{1}v_{2}^{\prime}$. Clearly
$v_{2},v_{2}^{\prime}\in S^{\prime}$ holds. Sort the points in $S^{\prime}$ in
radial order around $v_{1}$. Further let $v_{x}\in S^{\prime}$ be the next
vertex after $v_{2}$ in this radial order and $C$ be the plane spanning cycle
with edges $v_{1}v_{2}$ and $v_{1}v_{x}$, as guaranteed by Lemma 3.

By Conjecture 3, we can flip $P$ to $C\setminus v_{1}v_{x}$. Then, flipping
$v_{1}v_{2}$ to $v_{1}v_{x}$ we get to the path $C\setminus v_{1}v_{2}$, which
now has $v_{1}v_{x}$ as starting edge. We iteratively continue this process of
“rotating” the starting edge until reaching $v_{1}v_{2}^{\prime}$.∎

Theorems 1.1 and 1.2 imply that it suffices to show connectedness of certain
subgraphs of the flip graph. A priori it is not clear whether this is an
easier or a more difficult task – on the one hand we have smaller graphs,
making it easier to handle. On the other hand, we may be more restricted
concerning which flips we can perform, or exclude certain “nice” paths.

##  3 Flip Connectivity for Wheel Sets

Akl et al. [2] proved connectedness of the flip graph if the underlying point
set $S$ is in convex position. They showed that every path in $\mathcal{P}(S)$
can be flipped to a _canonical path_ that uses only edges on the convex hull
of $S$. To generalize this approach to other classes of point sets, we need
two ingredients: (i) a set of _canonical paths_ that serve as the target of
the flip operations and that have the property that any canonical path can be
transformed into any other canonical path by a simple sequence of flips,
usually of constant length; and (ii) a strategy to flip any given path to some
canonical path.

Recall that a set $S$ of $n\geq 4$ points in the plane is a _wheel set_ if
there is exactly one interior point $c_{0}\in S$. We call $c_{0}$ the _center_
of $S$ and classify the edges on $S$ as follows: an edge incident to the
center $c_{0}$ is called a _radial_ edge, and an edge along
$\operatorname{CH}(S)$ is called _spine_ edge (the set of spine edges forms
the _spine_ , which is just the boundary of the convex hull here). All other
edges are called _inner_ edges. The _canonical paths_ are those that consist
only of spine edges and one or two radial edges.

We need two observations. Let $S$ be a point set and
$P=v_{1},\ldots,v_{n}\in\mathcal{P}(S)$. Further, let $v_{i}$ $(i\geq 3)$ be a
vertex such that no edge on $S$ crosses $v_{1}v_{i}$. We denote the face
bounded by $v_{1},\ldots,v_{i},v_{1}$ by $\Phi(v_{i})$.

###### Observation 3.1

Let $S$ be a point set, $P=v_{1},\dots,v_{n}\in\mathcal{P}(S)$, and $v_{i}$
($i~{}\geq~{}3$) be a vertex such that no edge on $S$ crosses $v_{1}v_{i}$.
Then all vertices after $v_{i}$ (i.e., $\\{v_{i+1},\ldots,v_{n}\\}$) must
entirely be contained in either the interior or the exterior of $\Phi(v_{i})$.

###### Observation 3.2

Let $S$ be a wheel set and let $P=v_{1},\dots,v_{n}\in\mathcal{P}(S)$. Suppose
that the edge $v_{i}v_{i+1}$ of $P$ is an inner edge. Then the sets
$\\{v_{1},\dots,v_{i-1}\\}$ and $\\{v_{i+2},\dots,v_{n}\\}$ lie on different
sides of the line spanned by $v_{i}v_{i+1}$.

See 1.3

###### Proof

Let $P=v_{1},\dots,v_{n}\in\mathcal{P}(S)$ be a non-canonical path. W.l.o.g.,
we can assume $v_{1}\neq c_{0}$ (at least one of the two endpoints of $P$ is
not the center). We show how to apply suitable flips to increase the number of
spine edges of $P$.

By Lemma 2, the edge $v_{1}v_{2}$ is either radial or a spine edge. We
distinguish the two cases:

Case 1

$v_{1}v_{2}$ is radial, i.e., (since we assumed $v_{1}\neq c_{0}$), we have
$v_{2}=c_{0}$.

Then $v_{2}v_{3}$ is radial and, in analogy to Lemma 2, the remaining path can
only visit vertices on one side of $v_{1}v_{2}v_{3}$ (see Figure 6 (left)).
Hence, $v_{3}$ must be a neighbor of $v_{1}$ along the convex hull.

Thus we can increase the number of spine edges by flipping the radial edge
$v_{2}v_{3}$ to the spine edge $v_{1}v_{3}$.

Case 2

$v_{1}v_{2}$ is a spine edge.

Let $v_{a}$ ($a\neq 2$) be a neighbor of $v_{1}$ (along the convex hull). Note
first that we can assume $v_{a-1}v_{a}$ to be a spine edge, since otherwise we
can increase the number of spine edges by flipping $v_{a-1}v_{a}$ to
$v_{1}v_{a}$. Furthermore, we can assume $a\neq n$, since otherwise we can
insert $v_{1}v_{n}$ and remove an arbitrary (non-spine) edge.

By Observation 3.2, $P$ cannot have any inner edge $e$ before $v_{a}$, since
otherwise $e$ would have the neighbors $v_{1}$ and $v_{a}$ on the same side.
On the other hand, since $v_{1}v_{2}$ and $v_{a-1}v_{a}$ are spine edges,
$v_{a+1}$ must be in the interior of the face $\Phi(v_{a})$. Then, by
Observation 3.1, all extreme points must already be covered before $v_{a+1}$
(see Figure 6 (right)). This, however, implies that $P$ does not contain an
inner edge.

Hence, the case that $v_{1}v_{2}$ (and $v_{a-1}v_{a}$) are spine edges cannot
occur, since we assumed $P$ to be non-canonical, i.e., containing an inner
edge.

Figure 6:  _Left:_ Illustration of Case 1: if $v_{1}$ and $v_{3}$ are not
neighbors, there are vertices that cannot be reached. _Right:_ Illustration of
Case 2: if $v_{a-1}v_{a}$ is a spine edge, the path after $v_{a}$ cannot visit
any extreme point anymore.

Iteratively applying above procedure, we obtain a canonical path. Any two such
canonical paths can be transformed into each other by at most 4 flips.

By Observation 3.2 and the fact that not all edges can be radial, we know that
any plane spanning path contains at least one spine edge and hence, we need at
most $n-3$ iterations. In total, we need at most $2(n-3)+4=2n-2$ flips.
However, if we count a little more carefully, we see that in the case of $n-3$
iterations, i.e., only one radial edge remains and not two, we actually need
only two flips instead of 4 for the intermediate step. Hence, we save two
steps.∎

##  4 Flip Connectivity for Generalized Double Circles

The proof for generalized double circles is in principle similar to the one
for wheel sets but much more involved. For a point set $S$ and two extreme
points $p,q\in S$, we call a subset $CC(p,q)\subset S$ _concave chain_ (chain
for short) for $S$, if (i) $p,q\in CC(p,q)$; (ii) $CC(p,q)$ is in convex
position; (iii) $CC(p,q)$ contains no other extreme points of $S$; and (iv)
every line $\ell_{xy}$ through any two points $x,y\in CC(p,q)$ has the
property that all points of $S\setminus CC(p,q)$ are contained in the open
halfplane bounded by $\ell_{xy}$ that contains neither $p$ nor $q$. Note that
the extreme points $p$ and $q$ must necessarily be consecutive along
$\operatorname{CH}(S)$. If there is no danger of confusion, we also refer to
the spanning path from $p$ to $q$ along the convex hull of $CC(p,q)$ as the
concave chain.

Figure 7:  (a-c) Examples of generalized double circles (the uncrossed
spanning cycle is depicted in orange). (d) A point set admitting an uncrossed
spanning cycle that is _not_ a generalized double circle.

A point set $S$ is in _generalized double circle_ position if there exists a
family of concave chains such that every inner point of $S$ is contained in
exactly one chain and every extreme point of $S$ is contained in exactly two
chains. We denote the class of generalized double circles by $\mathsf{GDC}$
(see Figure 7 for an illustration). For $S\in\mathsf{GDC}$, it is not hard to
see that the union of the concave chains forms an uncrossed spanning cycle:

###### Lemma 4

Every point set $S\in\mathsf{GDC}$ admits an uncrossed spanning cycle formed
by the union of the concave chains.

###### Proof

Let $S\in\mathsf{GDC}$ and denote the extreme points of $S$ by
$u_{1},\dots,u_{k}$ in circular order. Assume, for the sake of contradiction,
that there is an edge $rs$ along the convex hull of a concave chain
$CC(u_{i},u_{i+1})$ that is crossed by some edge $pq$. Then $p$ and $q$ lie on
different sides of the line $\ell_{rs}$ through $rs$ and hence, at least one
of the points $p$ or $q$ must belong to $CC(u_{i},u_{i+1})$, say $q\in
CC(u_{i},u_{i+1})$. Furthermore, $\ell_{qs}$ or $\ell_{qr}$ must have $p$ on
the same side as $u_{i}$ or $u_{i+1}$ (note that this is also the case if $r$
or $s$ and $q$ coincide with $u_{i},u_{i+1}$); see Figure 8. Hence, also $p\in
CC(u_{i},u_{i+1})$ holds. However, since $rs$ is a hull edge of
$CC(u_{i},u_{i+1})$ it cannot be crossed by $pq$; a contradiction.∎

Figure 8: Illustration of the proof of Lemma 4.

Before diving into the details of the proof for generalized double circles, we
start by collecting preliminary results in a slightly more general setting,
namely for point sets $S$ fulfilling the following property:

(P1)

there is an _uncrossed_ spanning cycle $C$ on $S$, i.e., no edge joining two
points of $S$ crosses any edge of $C$.

A point set fulfilling (P1) is called _spinal_ point set. When considering a
spinal point set $S$, we first fix an uncrossed spanning cycle $C$, which we
call _spine_ and all edges in $C$ _spine edges_. For instance, generalized
double circles are spinal point sets and the spine is precisely the uncrossed
spanning cycle formed by the concave chains as described above. Whenever
speaking of the spine or spine edges for some point set without further
specification, the underlying uncrossed cycle is either clear from the
context, or the statement holds for any choice of such a cycle. Furthermore,
we call all edges in the exterior/interior of the spine _outer/inner edges_.

We define the _canonical paths_ to be those that consist only of spine edges.
Note that this definition also captures the canonical paths used by Akl et
al., and that any canonical path can be transformed into any other by a single
flip (of Type 2). Two vertices incident to a common spine edge are called
_neighbors_.

Next, we need a strategy to flip an arbitrary path to a canonical path. The
biggest issue is to ensure that all intermediate paths in the flip sequence
are plane. To this end, it is very helpful if many triangles that are spanned
by a spine edge and a third point of $S$ are _empty_ , i.e., do not contain
any other point from $S$ in their interior. In the extreme case, where all
such triangles are empty it is not hard to show that the flip graph is
connected. We omit the details as it turns out that only convex point sets
fulfill this extreme case (see Appendix 0.A).

### Valid flips.

We collect a few observations which will be useful to confirm the validity of
a flip. Whenever we apply more than one flip, the notation in subsequent flips
refers to the original graph and not the current (usually we apply one or two
flips in a certain step). Figure 9 gives an illustration of Observation 4.1.

Figure 9:  _Left to right:_ Illustration of the three flips in Observation
4.1. The spine is depicted in orange and edge flips are indicated by replacing
dashed edges for dotted (in the middle, the two flips must of course be
executed one after the other).

###### Observation 4.1

Let $S$ be a spinal point set, $P=v_{1},\dots,v_{n}\in\mathcal{P}(S)$, and
$v_{1},v_{a}$ ($a\neq 2$) be neighbors. Then the following flips are valid
(under the specified additional assumptions):

$\displaystyle(a$ $\displaystyle)\text{ flip }v_{a-1}v_{a}\text{ to
}v_{1}v_{a}$ $\displaystyle(b$ $\displaystyle)\text{ flip }v_{a}v_{a+1}\text{
to }v_{a-1}v_{a+1}$ $\displaystyle(c$ $\displaystyle)\text{ flip
}v_{a}v_{a+1}\text{ to }v_{1}v_{a+1}$

Strictly speaking, in Observation 4.1(c) we do not require $v_{a-1}v_{a}$ to
be a spine edge, but merely to be an edge not crossing $v_{1}v_{a+1}$. The
following lemma provides structural properties for generalized double circles,
if the triangles in Observation 4.1(b,c) are non-empty:

######  Lemma 5 ()

Let $S\in\mathsf{GDC}$ and $p,q,x\in S$ such that $p$ and $q$ are neighbors.
Further, let the triangle $\Delta pqx$ be non-empty. Then the following holds:

  1. (i)

At least one of the two points $p,q$ is an extreme point (say $p$),

  2. (ii)

$x$ does not lie on a common chain with $p$ _and_ $q$, but shares a common
chain with either $p$ or $q$ (the latter may only happen if $q$ is also an
extreme point).

Figure 10: Illustration of the proof of Lemma 5.

###### Proof

Concerning part (i), assume for the sake of contradiction that neither $p$ nor
$q$ is an extreme point and let $y\in\Delta pqx$. First recall that $p$ and
$q$ belong to exactly one concave chain and since they are neighbors, they
belong to the same chain – call it $C_{pq}$. Further note that $y$ is not an
extreme point and hence, also belongs to a unique concave chain.

Let us first consider the case that $x$ and $y$ share a common chain $C_{xy}$.
Since concave chains are in convex position, this cannot be $C_{pq}$. However,
since $y$ is contained in the interior of $\Delta pqx$, the line $\ell_{xy}$
through $x$ and $y$ separates $p$ and $q$; a contradiction to property (iv) of
the chain $C_{xy}$ (see Figure 10(a)).

Consider next, that $x$ and $y$ do not share a common chain. If $y$ does not
belong to $C_{pq}$, then neither of the points $p,q,x$ belongs to the chain
$C_{y}$ of $y$. However, any line through $y$ and another point of $C_{y}$
separates these three points; a contradiction to property (iv) of $C_{y}$ (see
Figure 10(b)). If $y$ belongs to $C_{pq}$, then either $p$ and $q$ are not
neighbors or the line $\ell_{pq}$ has $y$ and the extreme points (in $S$) of
$C_{pq}$ on the same side (see Figure 10(c) and Figure 10(d)); a contradiction
either way. This finishes the proof of part (i).

Concerning part (ii), first note that the extreme point $p$ belongs to two
chains $C_{pq}$ and $C_{p\bar{q}}$ (the former also contains $q$ while the
latter does not). Also assume that $q$ is not an extreme point. Then we need
to show that $x$ belongs to $C_{p\bar{q}}$.

First we argue that $x$ does not belong to $C_{pq}$. Indeed, if this was the
case, the point $y\in\Delta pqx$ (which does not belong to $C_{pq}$) would lie
on the same side of $\ell_{qx}$ as $p$ (see Figure 10(e)); a contradiction to
property (iv) of $C_{pq}$.

Second, suppose for the sake of contradiction that $x$ belongs to some other
chain $C\neq C_{p\bar{q}}$. Again we consider the two cases where $x$ and $y$
share a common chain or not.

First, let $x$ and $y$ share a common chain (which, as before, is not
$C_{pq}$). Since $\ell_{xy}$ separates $p$ and $q$ this is a contradiction,
except $p,x,y$ lie on a common chain, which however is excluded because
$x\notin C_{p\bar{q}}$ (see Figure 10(f)).

Second, let $x$ and $y$ not share a common chain. The cases that $y$ belongs
to a chain that is not $C_{p\bar{q}}$ are completely analogous as before (see
Figures 10(b,c,d)). Hence, it remains to consider $y\in C_{p\bar{q}}$. In this
case, the line $\ell_{py}$ separates $q$ and $x$; again a contradiction (see
Figure 10(g)).

The case that $q$ is an extreme point is now completely analogous. Figures
10(h,i) summarize the possible configurations for a non-empty triangle $\Delta
pqx$.∎

### Combinatorial distance measure.

In contrast to the proof for wheel sets, it may now not be possible anymore to
directly increase the number of spine edges and hence, we need a more
sophisticated measure. Let $C$ be the spine of a spinal point set $S$ and
$p,q\in S$. Further let $o\in\\{\text{cw},\text{ccw}\\}$ be an orientation. We
define the _distance_ between $p,q$ _in direction $o$_, denoted by
$d^{o}(p,q)$, as the number of spine edges along $C$ that lie between $p$ and
$q$ in direction $o$. Furthermore, we define the _distance_ between $p$ and
$q$ to be

$d(p,q)=\min\\{d^{\text{cw}}(p,q),d^{\text{ccw}}(p,q)\\}.$

Note that neighboring points along the spine have distance one. Using this
notion we define the _weight_ of an edge to be the distance between its
endpoints and the (overall) weight of a graph on $S$ to be the sum of its edge
weights.

Figure 11:  _Left:_ Illustration of Observation 4.2. One of the dashed edges
has smaller weight than the solid: $d(s,q)=4$; $d(s,p)=4$; $d(s,r)=3$.
_Right:_ Illustration of Lemma 6. The initial path is depicted by solid and
dashed edges. Flipping the dashed edges to the dotted edges increases the
number of spine edges.

Our goal will be to perform weight decreasing flips. To this end, we state two
more useful preliminary results (see also Figure 11):

###### Observation 4.2

Let $S$ be a spinal point set, $p,q,r$ be three neighboring points in this
order (i.e., $q$ lies between $p$ and $r$), and $s\in S\setminus\\{p,q,r\\}$
be another point. Then $d(p,s)<d(q,s)$ or $d(r,s)<d(q,s)$ holds.

Combining Observation 4.1 and Observation 4.2, it is apparent that we can
perform weight decreasing flips whenever $\Delta v_{a-1}v_{a}v_{a+1}$ and
$\Delta v_{1}v_{a}v_{a+1}$ are empty.

######  Lemma 6 ()

Let $S$ be a spinal point set, $P=v_{1},\ldots,v_{n}\in\mathcal{P}(S)$, and
$v_{a},v_{b}$ ($a,b\neq 2$) be neighbors of $v_{1}$ as well as $v_{c},v_{d}$
($c,d\neq n-1$) be neighbors of $v_{n}$. If $\max(a,b)>\min(c,d)$, then the
number of spine edges in $P$ can be increased by performing at most two flips,
which also decrease the overall weight of $P$.

###### Proof

Let $\max(a,b)>\min(c,d)$ and assume w.l.o.g. that $a>c$ holds. If
$v_{a-1}v_{a}$ or $v_{c}v_{c+1}$ is not a spine edge, we can increase the
number of spine edges by a single flip using Observation 4.1(a). Hence, we can
assume these edges to be spine edges, which implies that $v_{a}v_{a+1}$ and
$v_{c-1}v_{c}$ are not spine edges.

Then we flip the spine edge $v_{a-1}v_{a}$ to another spine edge $v_{1}v_{a}$
resulting in the path
$v_{a-1},\ldots,v_{c-1},v_{c},\ldots,v_{1},v_{a},\ldots,v_{n}$. Next, flipping
$v_{c-1}v_{c}$ to $v_{c}v_{n}$ is valid and now replaces a non-spine edge by a
spine edge. See Figure 11 (right) for an illustration.∎

Note that $v_{b}$ or $v_{d}$ in Lemma 6 may not exist, if the first or last
edge of $P$ is a spine edge. Lemma 6 essentially enables us to perform weight
decreasing flips whenever the path traverses a neighbor of $v_{n}$ before it
reached both neighbors of $v_{1}$. We are now ready to prove Theorem 1.4, but
briefly summarize the proof strategy from a high level perspective beforehand:

### High level proof strategy.

To flip an arbitrary path $P\in\mathcal{P}(S)$ to a canonical path, we perform
iterations of suitable flips such that in each iteration we either

  1. (i)

increase the number of spine edges along $P$ (while not increasing the overall
weight of $P$), or

  2. (ii)

decrease the overall weight of $P$ (while not decreasing the number of spine
edges along $P$).

Note that for the connectivity of the flip graph it is not necessary to
guarantee the non increasing overall weight in the first part. However, this
will provide us with a better bound on the diameter of the flip graph.

See 1.4

###### Proof

Let $P~{}=~{}v_{1},\dots,v_{n}~{}\in~{}\mathcal{P}(S)$ be a non-canonical
path. As described in the high level proof strategy in Section 4, we show how
to iteratively transform $P$ to a canonical path by increasing the number of
spine edges or decreasing its overall weight. As usual let $v_{a}$ ($a\neq 2$)
be a neighbor of $v_{1}$.

We can assume, w.l.o.g., that $v_{1}$ and $v_{n}$ are not neighbors, since
otherwise we can flip an arbitrary (non-spine) edge of $P$ to the spine edge
$v_{1}v_{n}$ (performing a Type 2 flip), i.e., $a<n$. Furthermore, we can also
assume w.l.o.g., that $v_{a-1}v_{a}$ is a spine edge, since otherwise we can
flip $v_{a-1}v_{a}$ to the spine edge $v_{1}v_{a}$ (Observation 4.1(a)). This
also implies that the edge $v_{a}v_{a+1}$, which exists because $a<n$, is not
a spine edge, since $v_{a}$ already has the two neighbors $v_{a-1}$ and
$v_{1}$.

We distinguish two cases – $v_{1}v_{2}$ being a spine edge or not:

Case 1

$v_{1}v_{2}$ is not a spine edge.

This case is easier to handle, since we are guaranteed that both neighbors
$v_{a},v_{b}$ $(a,b\neq 2)$ of $v_{1}$ are potential candidates to flip to. In
order to apply Observation 4.1, we require $\Delta v_{1}v_{a}v_{a+1}$ or
$\Delta v_{1}v_{b}v_{b+1}$ to be empty. So, let’s consider these two subcases
separately:

Case 1.1

$\Delta v_{1}v_{a}v_{a+1}$ (or analogously $\Delta v_{1}v_{b}v_{b+1}$) is
empty.

Then we apply the following two flips:

$\text{flip }v_{a}v_{a+1}\text{ to }v_{1}v_{a+1}\qquad\text{ and
}\qquad\text{flip }v_{1}v_{2}\text{ to }v_{1}v_{a},$

where the first flip results in the path
$v_{a},\ldots,v_{1},v_{a+1},\ldots,v_{n}$ (and is valid by Observation 4.1(c))
and the second flip then results in the path
$v_{2},\ldots,v_{a},v_{1},v_{a+1},\ldots,v_{n}$ (valid due to Observation
4.1(a)). The first flip replaces a non-spine edge by another non-spine edge
and may increase the weight by at most one. The second flip replaces a non-
spine by a spine edge, which also decreases the weight by at least one.
Together, the number of spine edges increases, while the overall weight does
not increase.

Case 1.2

$\Delta v_{1}v_{a}v_{a+1}$ and $\Delta v_{1}v_{b}v_{b+1}$ are not empty.

Lemma 5(i) implies that ($v_{1}$ or $v_{a}$) and ($v_{1}$ or $v_{b}$) is an
extreme point.

Case 1.2.1

$v_{1},v_{a},v_{b}$ are all extreme points.

The triangles $\Delta v_{1}v_{a}v_{a+1}$ and $\Delta v_{1}v_{b}v_{b+1}$ being
non-empty implies that both, $v_{a}v_{a+1}$ and $v_{b}v_{b+1}$ are outer edges
(see Figure 12(a)). Not both of them can contain $n/2$ points under222For an
outer edge $e$ (which necessarily connects two points from the same chain), we
say that the points along this chain between the two endpoints of $e$
(excluding the endpoints) lie _under_ $e$. its edge. Hence, one of the two
flips – replacing $v_{a}v_{a+1}$ by $v_{a-1}v_{a+1}$, or $v_{b}v_{b+1}$ by
$v_{b-1}v_{b+1}$ must be weight decreasing, say w.l.o.g. the one for $v_{a}$.
Then we apply the following flips:

$\text{flip }v_{a-1}v_{a}\text{ to }v_{1}v_{a}\qquad\text{ and
}\qquad\text{flip }v_{a}v_{a+1}\text{ to }v_{a-1}v_{a+1}.$

The first flip is valid due to Observation 4.1(a) (replacing a spine edge by
another spine edge) and the second is valid due to Observation 4.1(b) and
decreases the weight by assumption.

Case 1.2.2

$v_{1}$ and $v_{a}$ are extreme points and $v_{b}$ is not (analogous with
exchanged roles of $v_{a}$ and $v_{b}$).

In this case, using Lemma 5(ii), we conclude that the triangle $\Delta
v_{1}v_{b}v_{b+1}$ must be empty; a contradiction.

Case 1.2.3

$v_{1}$ is an extreme point and $v_{a},v_{b}$ are not.

By Lemma 5(ii), the edge $v_{a}v_{a+1}$ must be an inner edge between the two
concave chains of $v_{1}$. If $v_{a+1}$ is a neighbor of $v_{1}$ we can simply
replace $v_{a}v_{a+1}$ by $v_{1}v_{a+1}$ (Observation 4.1(a)). Otherwise, the
other neighbor $v_{b}$ of $v_{1}$ cannot be incident to an inner edge and
hence, $\Delta v_{1}v_{b}v_{b+1}$ is empty; a contradiction (see Figure
12(b)).

Figure 12: (a) Case 1.2.1. There cannot be more than $n/2$ points in each
yellow region and hence, at least one of the flips $v_{a}v_{a+1}$ to
$v_{a-1}v_{a+1}$ or $v_{b}v_{b+1}$ to $v_{b-1}v_{b+1}$ decreases the weight.
(b) Case 1.2.3. Either $\Delta v_{1}v_{a}v_{a+1}$ or $\Delta
v_{1}v_{b}v_{b+1}$ must be empty. (c) Case 1.2.4.

Case 1.2.4

$v_{1}$ is not an extreme point and $v_{a},v_{b}$ are both extreme points.

This case is analogous to Case 1.2.1. Again, both, $v_{a}v_{a+1}$ and
$v_{b}v_{b+1}$ must be outer edges and the regions under those two edges must
be disjoint (see Figure 12(c)). Hence, one of the two flips – replacing
$v_{a}v_{a+1}$ by $v_{a-1}v_{a+1}$, or $v_{b}v_{b+1}$ by $v_{b-1}v_{b+1}$ must
be weight decreasing, say w.l.o.g. the one for $v_{a}$. Then, as in Case
1.2.1, we apply the following flips:

$\text{flip }v_{a-1}v_{a}\text{ to }v_{1}v_{a}\qquad\text{ and
}\qquad\text{flip }v_{a}v_{a+1}\text{ to }v_{a-1}v_{a+1}.$

Case 2

$v_{1}v_{2}$ is a spine edge.

In this case we will consider $P$ from both ends $v_{1}$ and $v_{n}$. Our
general strategy here is to first rule out some easier cases and collect all
those cases where we cannot immediately make progress. For these remaining
“bad” cases we consider the setting from both ends of the path, i.e., we
consider all combinations of bad cases.

Case 2.1

$v_{1},v_{a}$ are not extreme points. And $v_{a-1}$ is also not an extreme
point. Then we either

  * •

flip $v_{a}v_{a+1}$ to $v_{1}v_{a+1}$, or

  * •

flip $v_{a-1}v_{a}$ to $v_{1}v_{a}$ and $v_{a}v_{a+1}$ to $v_{a-1}v_{a+1}$.

By Observation 4.2, one of the two choices decreases the overall weight and
all flips are valid because neither of the vertices $v_{1},v_{a},v_{a-1}$ is
an extreme point and hence, the triangles $\Delta v_{1}v_{a}v_{a+1}$ and
$\Delta v_{a-1}v_{a}v_{a+1}$ are empty.

Case 2.2

$v_{1},v_{a}$ are not extreme points. And $v_{a-1}$ is an extreme point.

Case 2.2.1

$v_{a-2}$ lies on the same chain as $v_{1}$.

Case 2.2.1.1

$d(v_{a-2}v_{a-1})=2$.

This implies $v_{a-2}$ to be an extreme point and there is only one other
point in $S$ that does not belong to the chain of $v_{a-2}$ and $v_{a-1}$; see
Figure 13(a). This, however, implies that both triangles $\Delta
v_{1}v_{a}v_{a+1}$ and $\Delta v_{a-1}v_{a}v_{a+1}$ are empty and hence, using
Obervation 4.1 and Observation 4.2, we can perform weight decreasing flips.

Case 2.2.1.2

$d(v_{a-2}v_{a-1})>2$.

Then we flip $v_{a-2}v_{a-1}$ to $v_{1}v_{a-1}$, which decreases the overall
weight, since $v_{1}v_{a-1}$ has weight 2. See Figure 13(b).

Case 2.2.2

$v_{a-2}$ lies on a different chain as $v_{1}$.

If $v_{a+1}$ lies in the exterior of $\Phi(v_{a})$, then
$v_{a-1},v_{a},v_{1},v_{a+1}$ share a common chain and we can apply the flips
of Case 2.1.

If $v_{a+1}$ lies in the interior of $\Phi(v_{a})$ this constitutes our first
“bad” case (note that Observation 3.1 implies that the subpath
$v_{a+1},\ldots,v_{n}$ does not contain any extreme point). Further, we can
assume $v_{a-2}v_{a-1}$ also to be a spine edge, since otherwise we flip
$v_{a-1}v_{a}$ to $v_{1}v_{a}$ and are back in Case 1. Also we can assume
$v_{a}v_{a+1}$ to be an inner edge towards the $v_{a-1}$ chain, since
otherwise we can make progress (using Observations 4.1 and 4.2) because both
triangles $\Delta v_{1}v_{a}v_{a+1}$ and $\Delta v_{a-1}v_{a}v_{a+1}$ would be
empty by Lemma 5(ii). See Figure 13(c).

Figure 13: (a) Case 2.2.1.1. (b) Case 2.2.1.2. Replace $v_{a-2}v_{a-1}$ by
$v_{1}v_{a-1}$. (c) The first “bad” case as described in Case 2.2.2. Figure
14: (a,b) The “bad” cases of Case 2.3. Either way, $v_{a}v_{a+1}$ is in the
interior of $\Phi(v_{a})$. (c,d) The two “bad” cases of Case 2.4. The edge
$v_{a}v_{a+1}$ is in the exterior of $\Phi(v_{a})$. (e,f) The two “bad” cases
of Case 2.5. The edge $v_{a}v_{a+1}$ can be in the interior (bottom) or
exterior (top) of $\Phi(v_{a})$. Recall that the dashed red arc shall
emphasize that there is no vertex lying on this chain between the two extreme
points $v_{1},v_{a}$.

Case 2.3

$v_{1}$ is an extreme point and $v_{a}$ is not an extreme point.

Again it suffices to consider the case that at least one of the triangles
$\Delta v_{1}v_{a}v_{a+1}$ or $\Delta v_{a-1}v_{a}v_{a+1}$ is non-empty.
Either way, again using Lemma 5(ii), this can only happen, if $v_{a+1}$ is in
the interior of $\Phi(v_{a})$, more precisely, $v_{a}v_{a+1}$ is an inner edge
towards one of the neighboring chains of the $v_{a}$ chain (where the one case
is only relevant if $v_{a-1}$ is an extreme point); see Figure 14(a,b). This
constitutes the second “bad” case. As before, there are no extreme points
along the subpath $v_{a+1},\ldots,v_{n}$.

Case 2.4

$v_{a}$ is an extreme point and $v_{1}$ is not an extreme point.

If $v_{a}v_{a+1}$ is an inner edge both triangles $\Delta v_{1}v_{a}v_{a+1}$
and $\Delta v_{a-1}v_{a}v_{a+1}$ are empty and hence, there are two “bad”
cases to consider here, namely when $v_{a}v_{a+1}$ is an outer edge (see
Figure 14(c,d)).

Case 2.5

$v_{1},v_{a}$ are extreme points.

Again, there are two “bad” cases to consider here, namely when $v_{a}v_{a+1}$
is an outer edge, or an inner edge to the $v_{1},v_{2}$ chain (see Figure
14(e,f)).

Let us summarize the six “bad” cases, where we cannot immediately make
progress (note that (II) comprises two cases but for the following arguments
it will not be important to distinguish between them):

  1. (I)

$v_{1},v_{a}$ are not extreme points, $v_{a-1}$ is an extreme point,
$v_{a}v_{a+1}$ is an inner edge towards the $v_{a-1}$ chain that does not
contain $v_{1}$, and $v_{a-1}v_{a-2}$ is a spine edge (Figure 13(c)).

  2. (II)

$v_{1}$ is an extreme point, $v_{a}$ is not an extreme point, and
$v_{a}v_{a+1}$ is an inner edge towards a neighboring chain (in the one case
$v_{a-1}$ must be extreme); Figure 14(a,b).

  3. (IIIa)

$v_{1}$ is not an extreme point, $v_{a}$ is an extreme point, and
$v_{a}v_{a+1}$ is an outer edge on the $v_{a-1}$ chain (Figure 14(c)).

  4. (IIIb)

$v_{1}$ is not an extreme point, $v_{a}$ is an extreme point, and
$v_{a}v_{a+1}$ is an outer edge on the $v_{1}$ chain (Figure 14(d)).

  5. (IVa)

$v_{1},v_{a}$ are extreme points and $v_{a}v_{a+1}$ is an outer edge (Figure
14(e)).

  6. (IVb)

$v_{1},v_{a}$ are extreme points and $v_{a}v_{a+1}$ is an inner edge to the
$v_{1}$ chain (Figure 14(f)).

In the remainder of the proof we settle these “bad” cases by arguing about
both ends of the path, i.e, we consider all $\binom{6}{2}+6=21$ combinations
of these “bad” cases. Recall that the order at the $v_{n}$ end must be thought
of as inverted, e.g., the analogue of $v_{a-1}v_{a}$ is $v_{c}v_{c+1}$ and the
analogue of $v_{a}v_{a+1}$ is $v_{c-1}v_{c}$.

Further note that there two non-isomorphic ways two realize a combination of
“bad” cases (see Figure 15). Furthermore, there are two ways to connect the
“loose” ends of the fixed structures with each other (one case where we have
$a<c$ and another where we have $c<a$). However, by Lemma 6, only the former
is of interest.

Figure 15:  The two non-isomorphic ways to realize a combination of “bad”
cases ((IIIa)+(IVa) is drawn here). Recall that the red dashed arc indicates
that there are no more vertices on this chain.

Since we are not using the edges of the intermediate subpaths, we are mostly
interested in the question whether or not a certain combination can be
realized in a plane manner (in one of the two ways) or not.

Fortunately, we can immediately exclude several combinations with the
following observations:

  1. 1.

As noted above, we can assume $a<c$ and hence, no “bad” case where $v_{a+1}$
is in the interior of $\Phi(v_{a})$ can be combined with a “bad” case having
$v_{n}$ or $v_{c}$ as extreme point. Hence, we can exclude all combinations
involving (I), (II), or (IVb), except (I)+(I). In fact, (I)+(I) is also not
possible as the path starting from $v_{1}$ would first need to traverse
$v_{c+1}$, then $v_{a}$ and then $v_{c}$, which is not possible.

  2. 2.

If $v_{a}v_{a+1}$ is an outer edge, there is always an “easy” flip possible to
either $v_{1}$ or $v_{a-1}$ (depending on which lies on the same chain as
$v_{a}$ and $v_{a+1}$). Hence, similar to Case 1.2.4, we can rule out cases by
showing that the regions (towards we flip $v_{a}v_{a+1}$ and $v_{c-1}v_{c}$
to) are disjoint. Also, we need to consider a subtle edge case, namely when
$v_{a}v_{a+1}$ and $v_{c-1}v_{c}$ coincide. We consider the remaining six
cases separately, as depicted in Figure 16. As depicted there, we have
disjoint regions in all 6 remaining combinations except for the edge cases
where the edges $v_{a}v_{a+1}$ and $v_{c-1}v_{c}$ coincide.

Figure 16: The remaining combinations where we try to find disjoint regions
each having to contain at least half of the point set. Edge cases are those
cases where the edges $v_{a}v_{a+1}$ and $v_{c-1}v_{c}$ coincide.

Hence, 1. and 2. rule out all possible cases, except the 6 edge cases from 2.,
where also these regions (containing at least $n/2$ points) coincide on the
chain $CC(v_{a},v_{c})$. These can be resolved as follows. In all cases there
exists an inner edge $v_{x-1}v_{x}$ along the path $v_{2}\ldots v_{a-1}$ that
is “closest” to $v_{1}$ and $v_{x}$ lies on the chain $CC(v_{a},v_{c})$. By
closest we mean that $v_{1}v_{x}$ does not intersect the path. Hence, flipping
$v_{x-1}v_{x}$ to $v_{1}v_{x}$ forms a valid flip and at least one of the two
choices (either from the $v_{1}$ end or $v_{n}$) decreases the weight. This
argument is analogous in all six edge cases, with the only difference that we
may replace $v_{1}$ by $v_{a-1}$ by first flipping $v_{a-1}v_{a}$ to
$v_{1}v_{a}$ if $v_{1}$ lies on the $CC(v_{a},v_{c})$ chain.

Recursively applying above process, we will eventually transform $P$ to a
canonical path that consists only of spine edges (the only paths with minimum
overall weight). Doing the same for $Q$ and noting that any pair of canonical
paths can be transformed into each other by a single flip, the connectedness
of the flip graph follows.

Concerning the required number of flips, note that any edge has weight at most
$\frac{n}{2}-1$ and the path has $n-1$ edges. Hence, the total number of
iterations to transform $P$ into a canonical path is at most

$\left(\left(n-1\right)\cdot\left(\frac{n}{2}-2\right)+(n-1)\right)\in
O(n^{2})$

Furthermore, any iteration requires at most two flips and hence, the total
number of flips to transform $P$ into $Q$ is still in $O(n^{2})$.∎

##  5 Conclusion

In this paper, we made progress towards a positive answer of Conjecture 1,
though it still remains open in general. We approached Conjecture 1 from two
directions and believe that Conjecture 3 might be easier to tackle, e.g. for
an inductive approach. For all our results we used only Type 1 and Type 2
flips (which can be simulated by Type 1 flips). It is an intriguing question
whether Type 3 flips are necessary at all.

Concerning the approach of special classes of point sets, of course one can
try to further adapt the ideas to other classes. Most of our results hold for
the setting of spinal point sets; the main obstacle that remains in order to
show flip connectivity in the (P1) setting would be to adapt Lemma 5. A proof
for general point sets, however, seems elusive at the moment.

Lastly, there are several other directions for further research conceivable,
e.g. considering simple drawings (or other types of drawings) instead of
straight-line drawings.

## References

  * [1] Aichholzer, O., Aurenhammer, F., Krasser, H.: Enumerating order types for small point sets with applications. Order 19, 265–281 (2002). https://doi.org/https://doi.org/10.1023/A:1021231927255, https://link.springer.com/article/10.1023/A:1021231927255
  * [2] Akl, S.G., Islam, M.K., Meijer, H.: On planar path transformation. Information Processing Letters 104(2), 59–64 (2007). https://doi.org/https://doi.org/10.1016/j.ipl.2007.05.009, https://www.sciencedirect.com/science/article/pii/S0020019007001366
  * [3] Bose, P., Hurtado, F.: Flips in planar graphs. Computational Geometry 42(1), 60–80 (2009). https://doi.org/https://doi.org/10.1016/j.comgeo.2008.04.001, https://www.sciencedirect.com/science/article/pii/S0925772108000370
  * [4] Chang, J.M., Wu, R.Y.: On the diameter of geometric path graphs of points in convex position. Information Processing Letters 109(8), 409–413 (2009). https://doi.org/https://doi.org/10.1016/j.ipl.2008.12.017, https://www.sciencedirect.com/science/article/pii/S0020019008003827
  * [5] Hernando, C., Hurtado, F., Noy, M.: Graphs of non-crossing perfect matchings. Graphs and Combinatorics 18(3), 517–532 (2002)
  * [6] Houle, M., Hurtado, F., Noy, M., Rivera-Campo, E.: Graphs of triangulations and perfect matchings. Graphs and Combinatorics 21, 325–331 (09 2005). https://doi.org/10.1007/s00373-005-0615-2
  * [7] Lawson, C.L.: Transforming triangulations. Discrete mathematics 3(4), 365–372 (1972)
  * [8] Nichols, T.L., Pilz, A., Tóth, C.D., Zehmakan, A.N.: Transition operations over plane trees. Discrete Mathematics 343(8), 111929 (2020). https://doi.org/https://doi.org/10.1016/j.disc.2020.111929, https://www.sciencedirect.com/science/article/pii/S0012365X20301217
  * [9] Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4) (2018). https://doi.org/10.3390/a11040052, https://www.mdpi.com/1999-4893/11/4/52
  * [10] Wagner, K.: Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung 46, 26–32 (1936), http://eudml.org/doc/146109

##  Appendix 0.A Only convex point sets fulfill the empty triangle property

###### Lemma 7

Let $S$ be a point set (in general position) such that there is a plane (not
necessarily uncrossed) spanning cycle $C$ on $S$ and any triangle using an
edge of $C$ is empty (i.e., does not contain a point of $S$). Then $S$ is in
convex position.

###### Proof

Assume, for the sake of contradiction, that $S$ is not in convex position, and
let $C$ be a plane spanning cycle (defining a non-convex simple polygon). It
is well-known that any non-convex polygon has at least one reflex interior
angle, say at vertex $r$ and further let $s$ be a neighbor of $r$ (along $C$).
Cearly, the line through $rs$ intersects $C$ in an edge $pq$ and hence, either
$\Delta pqr$ contains $s$ or $\Delta pqs$ contains $r$; a contradiction either
way.