Reconfigurations of Plane Caterpillars and Paths

Given a set of structures $C$, and a reconfiguration operation that transforms one object in $C$ to another, the reconfiguration graph is a graph with vertex set $C$ in which two vertices form an edge if one can be transformed into the other using a single reconfiguration operation. Often, in computer science, objects are solutions to a problem and reconfigurations are local changes that transform one solution into another. Then, to understand the solution space, it is important to study the reconfiguration graph. For an introduction to the topic, see [14].

Given a point set $S$ in the plane, a plane spanning tree on $S$ is a spanning tree of $S$ whose edges are straight line segments that do not cross. Let $𝒯(S)$ be the set of all plane spanning trees on $S$. We consider five reconfigurations on $𝒯(S)$ (see Figure 1). For the following, we are given $T_1=(S,E_1),T_2=(S,E_2)\in 𝒯(S)$, and we say that:

1. 1.

   $T_1$ and $T_2$ are connected by a flip if $E_2=E_1\setminus \{e\}\cup \{f\}$ for some edges $e,f$.

2. 2.

   $T_1$ and $T_2$ are connected by a compatible flip if $E_2=E_1\setminus \{e\}\cup \{f\}$ for some edges $e,f$ which do not cross.

3. 3.

   $T_1$ and $T_2$ are connected by a rotation if $E_2=E_1\setminus \{e\}\cup \{f\}$ for some edges $e,f$ which share an endpoint.

4. 4.

   $T_1$ and $T_2$ are connected by an empty triangle rotation if $E_2=E_1\setminus \{e\}\cup \{f\}$ for some edges $e,f$ which share an endpoint and the triangle spanned by their endpoints is empty.

5. 5.

   $T_1$ and $T_2$ are connected by a slide if $E_2=E_1\setminus \{e\}\cup \{f\}$ for some edges $e,f$ which are as in $4.$ and if $e=ab$ and $f=ac$ then $bc\in E_1\cap E_2$.

Note that every slide is an empty triangle rotation, every empty triangle rotation is a rotation, and so on. This hierarchy will be useful when studying the structural properties of the corresponding reconfiguration graphs.

The reconfiguration graphs associated with the operations described above have been a topic of interest for a long time with many results appearing through the years. These results have concerned connectivity [1, 7, 13], lower and upper bounds on the diameter [2, 9, 10], etc.

It is known that the reconfiguration graph of plane spanning trees is connected even in the most restrictive case when the reconfigurations are slides [1]. In the case of slides, a tight $\mathrm{\Theta }(n^2)$ bound on the diameter is shown in [4]. For the empty triangle rotations, an upper bound of $O(n\log n)$ on the diameter was shown in [13], while for the remaining reconfigurations, a linear upper bound is known [7]. In [2], an upper bound of $2n-3$ is shown for flip graphs. The best known lower bound on the diameter of the reconfiguration graphs is $\frac{14}{9}n-O(1)$, as per [8].

However, there has been little research on induced subgraphs of these reconfiguration graphs. The only such subgraph that has been explored is the one induced by plane spanning paths. For a set of $n$ points in convex position, it is known that the flip graph is connected [5] and that it has diameter $2n-5$ for $n\in \{3,4\}$ and $2n-6$ for $n\ge 5$ [11]. The flip graph of point sets with at most two convex layers is connected [12], as is the flip graph of generalized double circles [3]. For point sets in general position, connectivity was first conjectured by Akl, Islam and Meijer [5] 18 years ago but still remains unsolved.

We further the study of induced subgraphs of reconfiguration graphs of plane spanning trees by exploring reconfigurations of plane spanning caterpillars, and by expanding on the topic of reconfigurations of plane spanning paths. A caterpillar is a tree in which all non-leaf vertices form a path. We call this path the spine of the caterpillar. A plane spanning caterpillar of a point set $S$ is a plane spanning tree of $S$ which is a caterpillar. For a set $S$, we will denote by $𝒞(S)$ the set of all plane spanning caterpillars on $S$. We will denote the reconfiguration graphs on $𝒞(S)$ by $G_{𝒞}^{\text{flip}}(S)$, $G_{𝒞}^{\text{comp-flip}}(S)$, $G_{𝒞}^{\text{rot}}(S)$, $G_{𝒞}^{\text{emp-rot}}(S)$, and $G_{𝒞}^{\text{slide}}(S).$ First, we focus on the case when $S$ is in convex position. We show that the slide graph $G_{𝒞}^{\text{slide}}$ is connected, which implies that all of the reconfiguration graphs are connected in this case. For compatible flips, we prove a stronger bound for the diameter.

Next, we consider the case when $S$ is a point set in general position. For a caterpillar $C\in 𝒞(S)$, and consecutive spine vertices $v_i,\mathrm{\dots },v_j$ of $C$, we write $S_{i,j}$ for the point set consisting of the spine vertices and all of the leaves attached to them. We call $C\in 𝒞(S)$ with spine $v_1,v_2,\mathrm{\dots },v_k$ a well-separated caterpillar if for each $i\ge 1$, the convex hull of $S_{1,i}$ is disjoint from the rest of $S$. We can prove that all caterpillars in this class are mutually connected in $G_{𝒞}^{\text{slide}}(S)$. This large connected component is significant, as we can also show that $G_{𝒞}^{\text{slide}}(S)$ is disconnected. On the other hand, we can prove that the rotation graph $G_{𝒞}^{\text{rot}}(S)$ is connected. We leave open the question of the connectivity of $G_{𝒞}^{\text{emp-rot}}$.

Lastly, we focus on connected components of the reconfiguration graph of plane spanning paths. Given a set of points in general position $S$, we will call the corresponding flip graph of plane spanning paths $G_{𝒫}(S)$. Currently, the main open problem is deciding whether $G_{𝒫}(S)$ is connected. Here we find a large connected component consisting of what we call generalized peeling paths. We note that Theorem 6 was independently discovered by Kleist, Kramer, and Rieck [12]. We use the number of these paths to prove that there are at least $\frac{1}{4}(3^n-1)$ well-separated caterpillars on $S$. Finally, we investigate the minimal size of components in $G_{𝒫}(S)$.