Short Flip Sequences to Untangle Segments in the Plane

*

Guilherme da Fonseca, Yan Gerard, Bastien Rivier

► To cite this version:

Guilherme da Fonseca, Yan Gerard, Bastien Rivier. Short Flip Sequences to Untangle Segments in the Plane *. WALCOM 2024, Mar 2024, Kanazawa, Ishikawa, Japan. pp.163-178, 10.1007/978-981-97-0566-5_13 . hal-04505473

HAL Id: hal-04505473

https://hal.science/hal-04505473v1

Submitted on 14 Mar 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Short Flip Sequences to Untangle Segments in the Plane*

Guilherme D. da Fonseca¹[0000-0002-9807-028X], Yan
Gerard²[0000-0002-2664-0650], and Bastien Rivier²[0000-0001-5985-2169]

¹ Aix-Marseille Université and LIS, France.
guilherme.fonseca@lis-lab.fr

² Université Clermont Auvergne and LIMOS, France.
{yan.gerard, bastien.rivier}@uca.fr

**Abstract.** A (multi)set of segments in the plane may form a TSP tour, a matching, a tree, or any multigraph. If two segments cross, then we can reduce the total length with the following *flip* operation. We *remove* a pair of crossing segments, and *insert* a pair of non-crossing segments, while keeping the same vertex degrees. The goal of this paper is to devise efficient strategies to flip the segments in order to obtain crossing-free segments after a small number of flips. Linear and near-linear bounds on the number of flips were only known for segments with endpoints in convex position. We generalize these results, proving linear and near-linear bounds for cases with endpoints that are not in convex position. Our results are proved in a general setting that applies to multiple problems, using multigraphs and the distinction between removal and insertion choices when performing a flip.

**Keywords:** Planar geometry · Reconfiguration · Matching · Euclidean TSP.

## 1 Introduction

The *Euclidean Travelling Salesman Problem (TSP)* is one of the most studied geometric optimization problems. We are given a set *P* of points in the plane and the goal is to find a tour *S* of minimum length. While the optimal solution has no crossing segments, essentially all approximation algorithms, heuristics, and PTASs may produce solutions *S* with crossings. Given *S*, the only procedure known to obtain a solution *S'* without crossings and of shorter length is to perform a flip operation. In our case, a *flip* consists of *removing* a pair of crossing segments, and then *inserting* a pair of non-crossing segments preserving a tour (and consequently reducing its length). Flips are performed in *sequence* until a crossing-free tour is obtained, in a procedure called *untangle*.

The same flip operation may be applied in other settings. More precisely, a *flip* consists of removing a pair of crossing segments *s*₁, *s*₂ and inserting a

<footnote>* This work is supported by the French ANR PRC grant ADDS (ANR-19-CE48-0005).
Full version: https://arxiv.org/abs/2307.00853.</footnote>
pair of segments $s'_1, s'_2$ in a way that $s_1, s'_1, s_2, s'_2$ forms a cycle and a certain graph *property* is preserved. In the case of TSP tours, the property is being a Hamiltonian cycle. Other properties have also been studied, such as spanning trees, perfect matchings, and multigraphs. Notice that flips preserve the degrees of all vertices and multiple copies of the same edge may appear when we perform a flip on certain graphs.

When the goal is to obtain a crossing-free TSP tour, we are allowed to *choose* which pair of crossing segments to remove in order to perform fewer flips, which we call *removal choice* (Figure 1(a)). Notice that, in a tour, choosing which pair of crossing edges we remove defines which pair of crossing edges we insert. However, this is not the case for matchings and multigraphs. There, we are also allowed to choose which pair of segments to insert among two possibilities, which we call *insertion choice* (Figure 1(b)).

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** (a) Three untangle sequences for a tour with different removal choices. (b) Three untangle sequences for a matching with different insertion choices. We highlight the segments removed and inserted at each flip.</figcaption></figure>

Using removal or insertion choices to obtain shorter flip sequences has not been explicitly studied before and opens several new questions, while unifying the solution to multiple reconfiguration problems. Next, we describe previous work according to which choices are used. Throughout, *P* denotes the set of points and *n* the number of segments.

**Using no choice:** The *length* (i.e. the number of flips) of any untangle sequence for a TSP tour is $O(n^3)$ [22] and it is easy to construct $\Omega(n^2)$ examples. The same proof has been rediscovered in the context of matchings [9] after 35 years. If *P* is in convex position, then the number of crossings decreases at each flip, which gives a tight bound of $\Theta(n^2)$. If all points except the endpoints of *t* segments are in convex position, then the authors [15] recently showed a bound of $O tn^2$.

**Using only insertion choice:** It is possible to untangle a matching using only insertion choice and $O(n^2)$ flips [9]. Let $\sigma$ be the *spread* of *P*, that is, the ratio between the maximum and minimum distances among points in *P*. Using insertion choice, it is also possible to untangle a matching using $O(n\sigma)$ flips [7].

**Using only removal choice:** If *P* is in convex position, then by using $O(n)$ flips we can untangle a TSP tour [25,28], as well as a red-blue matching [7], while
the best known bound for trees is $O(n \log n)$ [7]. If instead of convex position, we
have colinear red points in a red-blue matching, then $O(n^2)$ flips suffice [7,12].

**Using both removal and insertion choices:** If $P$ is in convex position, then by using $O(n)$ flips we can untangle a matching [7].

## 1.1 New Results

Previous results are usually stated for a single graph property. Using choices, we are able to state the results in a more general setting. Proofs that use insertion choice are unlikely to generalize to red-blue matchings, TSP tours, or trees, where insertion choice is not available (still, they may hold for both non-bipartite matchings and multigraphs). In contrast, bounds for multigraphs using only removal choice apply to all these cases. Previously, we only knew linear or near-linear bounds when the points $P$ are in convex position and removal choice is available. The goal of the paper is to obtain linear and near-linear bounds to as many cases as possible, considering near-convex configurations as well as removal and insertion choices.

Let $P = C \cup T$ where $C$ is in convex position and the points of $T$ are outside the convex hull of $C$, unless otherwise specified. Let $S$ be a multiset of $n$ segments with endpoints $P$ and $t$ be the number of segments with at least one endpoint in $T$. We prove the following results to untangle $S$, and some are summarized in Table 1.

**Using only insertion choice (Section 2):** If $T = \emptyset$, then $O(n \log n)$ flips suffice. If $T$ is separated from $C$ by two parallel lines, then $O(tn \log n)$ flips suffice.

**Using only removal choice (Section 3):** If $|T| \le 2$ and $t = O(1)$, then $O(n \log n)$ flips suffice. In this case, our results hold with the points $T$ being anywhere with respect to the convex hull of $C$, however, if both points are outside, then $S$ must be a matching. As the bound for $|T| \le 1$ holds for trees, it is useful to compare it against the $O(n \log n)$ bound for trees in the convex case from [7] that strongly uses the fact that $S$ forms a tree. The $O(\log n)$ factor is not present for the special cases of TSP tours and red-blue matchings.

**Using both removal and insertion choices (Section 4):** If $T$ is separated from $C$ by two parallel lines, then $O(tn)$ flips suffice. If $T$ is anywhere outside the convex hull of $C$ and $S$ is a matching, then $O(t^3n)$ flips suffice.

In a matching or TSP tour, we have $t = O(|T|)$ and $n = O(|P|)$, however in a tree, $t$ can be as high as $O(|T|^2)$. In a multigraph $t$ and $n$ can be much larger than $|T|$ and $|P|$. The theorems describe more precise bounds as functions of all these parameters. For simplicity, the introduction only shows bounds in terms of $n$ and $t$.

## 1.2 Related Reconfiguration Problems

Combinatorial reconfiguration studies the step-by-step transition from one solution to another, for a given combinatorial problem. Many reconfiguration problems are presented in [18]. We give a brief overview of reconfiguration among line segments using alternative flip operations.
<table><caption>**Table 1.** Upper bounds to different versions of the problem with points having $O(1)$ degree. The letter R corresponds to removal choice, I to insertion choice, and $\emptyset$ to no choice. New results are highlighted in yellow with the theorem number in parenthesis and tight bounds are bold.</caption><thead><tr><th>Property:</th><th colspan="4">Matching</th><th colspan="2">TSP, Red-Blue</th></tr><tr><th>Choices:</th><th>RI</th><th>I</th><th>R</th><th>Ø</th><th>R</th><th>Ø</th></tr></thead><tbody><tr><td>Convex</td><td><b>n</b> [7]</td><td><i>n log n</i> (Thm 1)</td><td><i>n log n</i> (Thm 3)</td><td><i>n</i><sup>2</sup></td><td><b>n</b> [7,25,28]</td><td><i>n</i><sup>2</sup></td></tr><tr><td>|T| = 1</td><td><b>n</b> (Thm 8)</td><td><i>n log n</i> (Thm 2)</td><td><i>n log n</i> (Thm 4)</td><td><i>n</i><sup>2</sup> [15]</td><td><b>n</b> (Thm 4)</td><td><i>n</i><sup>2</sup> [15]</td></tr><tr><td>|T| = 2</td><td><b>n</b> (Thm 9)</td><td><i>n</i><sup>2</sup> [9]</td><td><i>n log n</i> (Thm 5)</td><td><i>n</i><sup>2</sup> [15]</td><td><b>n</b> (Thm 5)</td><td><i>n</i><sup>2</sup> [15]</td></tr><tr><td>separated</td><td><i>tn</i> (Thm 8)</td><td><i>tn log n</i> (Thm 2)</td><td><i>tn</i><sup>2</sup> [15]</td><td></td><td></td><td></td></tr><tr><td>C ∪ T</td><td><i>t</i><sup>3</sup><b>n</b> (Thm 9)</td><td><i>n</i><sup>2</sup> [9]</td><td><i>tn</i><sup>2</sup> [15]</td><td></td><td></td><td></td></tr></tbody></table>

The 2OPT flip is not restricted to crossing segments. It removes and inserts pairs of segments (the four segments forming a cycle) as the total length decreases. In contrast to flips among crossing segments, the number of 2OPT flips performed may be exponential [13].

It is possible to relax the flip definition even further to all operations that replace two segments by two others forming a cycle [5,6,8,10,14,27]. This definition has also been considered for multigraphs [16,17,20].

Another type of flip consists of removing a single segment and inserting another one. Such flips are widely studied for triangulations [3,19,21,23,24,26]. They have also been considered for non-crossing trees [1] and paths. It is possible to reconfigure any two non-crossing paths if the points are in convex position [4,11] or if there is one point inside the convex hull [2].

## 1.3 Preliminaries

Throughout, we consider multigraphs ($P, S$) whose vertices $P$ (called *endpoints*) are points in the plane and edges $S$ are a multiset of line segments. We assume that the endpoints are in *general position* and that the two endpoints of a segment are distinct. Given two (possibly equal) sets $P_1, P_2$ of endpoints, we say that a segment is a $P_1P_2$-segment if one endpoint is in $P_1$ and the other is in $P_2$. Similarly, we say that a segment is a $P_1$-segment if at least one endpoint is in $P_1$.

We say that two segments *cross* if they intersect at a single point that is not an endpoint of either segment. We say that a line *crosses* a segment if they intersect at a single point that is not an endpoint of the segment. We say that a segment or a line *separates* a set of points $P$ if $P$ can be partitioned into two non-empty sets $P_1, P_2$ such that every segment $p_1p_2$ with $p_1 \in P_1, p_2 \in P_2$ crosses $h$. Several proofs in this paper use the following two lemmas from previous papers.

**Lemma 1 ([22]).** Given a multiset $S$ of segments and a line $\ell$, let the line potential of $\ell$, denoted $\lambda(\ell)$, be the number of segments in $S$ crossing $\ell$. Then, $\lambda(\ell)$ never increases at a flip.
**Lemma 2 ([9]).** Consider a partition $S = \bigcup_i S_i$ of the multiset $S$ of segments and let $P_i$ be the set of endpoints of $S_i$. If no segment of $\binom{P_i}{2}$ crosses a segment of $\binom{P_j}{2}$ for $i \neq j$, then the sequences of flips in each $S_i$ are independent.

We say that a segment $s$ is *uncrossable* if for any two endpoints $p_1, p_2$, we have that $p_1p_2$ do not cross $s$. Lemma 2 implies that an uncrossable segment cannot be flipped.

Our bounds often have terms like $O(tn)$ and $O(n \log |C|)$ that would incorrectly become 0 if $t$ or $\log |C|$ is 0. In order to avoid this problem, factors in the $O$ notation should be made at least 1. For example, the aforementioned bounds should be respectively interpreted as $O((1+t)n)$ and $O(n \log(2 + |C|))$.

# 2 Insertion Choice

In this section, we show how to untangle a multigraph using only insertion choice, that is, our strategies do not choose which pair of crossing segments is removed, but only which pair of segments with the same endpoints is subsequently inserted. We start with the convex case, followed by points outside the convex separated by two parallel lines.

## 2.1 Convex

Let $P = C = \{p_1, \dots, p_{|C|}\}$ be a set of points in convex position sorted in counterclockwise order along the convex hull boundary (Figure 2(a)). Given a segment $p_a p_b$, we define the depth $\delta(p_a p_b) = |b-a|$. This definition resembles but is not the same as the depth used in [7]. We use the depth to prove the following theorem.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** (a) A multigraph $(C, S)$ with $|C| = 14$ points in convex position and $n = 9$ segments. (b) Insertion choice for Cases 1 and 2 of the proof of Theorem 1. (c) Insertion choice for Case 3.</figcaption></figure>

**Theorem 1.** Every multigraph $(C, S)$ with $C$ in convex position has an untangle sequence of length $O(n \log |C|) = O(n \log n)$ using only insertion choice, where $n = |S|$.
*Proof.* Let the potential function $\phi(S) = \prod_{s \in S} \delta(s)$. As $\delta(s) \in \{1, \dots, |C| - 1\}$, we have that $\phi(S)$ is integer, positive, and at most $|C|^n$. Next, we show that for any flipped pair of segments $p_a p_b, p_c p_d$ there exists an insertion choice that multiplies $\phi(S)$ by a factor of at most 3/4, and the theorem follows.

Consider a flip of a segment $p_a p_b$ with a segment $p_c p_d$ and assume without loss of generality that $a < c < b < d$. The contribution of the pair of segments $p_a p_b, p_c p_d$ to the potential $\phi(S)$ is the factor $f = \delta(p_a p_b) \delta(p_c p_d)$. Let $f'$ be the factor corresponding to the pair of inserted segments.

**Case 1:** If $\delta(p_a p_c) \le \delta(p_c p_b)$, then we insert the segments $p_a p_c$ and $p_b p_d$ and we get $f' = \delta(p_a p_c)\delta(p_b p_d)$ (Figure 2(b)). We notice $\delta(p_a p_b) = \delta(p_a p_c) + \delta(p_c p_b)$. It follows $\delta(p_a p_c) \le \delta(p_a p_b)/2$ and we have $\delta(p_b p_d) \le \delta(p_c p_d)$ and then $f' \le f/2$.

**Case 2:** If $\delta(p_b p_d) \le \delta(p_c p_b)$, then we insert the same segments $p_a p_c$ and $p_b p_d$ as previously. We have $\delta(p_a p_c) \le \delta(p_a p_b)$ and $\delta(p_b p_d) \le \delta(p_c p_d)/2$, which gives $f' \le f/2$.

**Case 3:** If (i) $\delta(p_a p_c) > \delta(p_c p_b)$ and (ii) $\delta(p_b p_d) > \delta(p_c p_b)$, then we insert the segments $p_a p_d$ and $p_c p_b$ (Figure 2(c)). The contribution of the new pair of segments is $f' = \delta(p_a p_d)\delta(p_c p_b)$. We introduce the coefficients $x = \frac{\delta(p_a p_c)}{\delta(p_c p_b)}$ and $y = \frac{\delta(p_b p_d)}{\delta(p_c p_b)}$ so that $\delta(p_a p_c) = x\delta(p_c p_b)$ and $\delta(p_b p_d) = y\delta(p_c p_b)$. It follows that $\delta(p_a p_b) = (1+x)\delta(p_c p_b)$, $\delta(p_c p_d) = (1+y)\delta(p_c p_b)$ and $\delta(p_a p_d) = (1+x+y)\delta(p_c p_b)$. The ratio $f'/f$ is equal to a function $g(x, y) = \frac{1+x+y}{(1+x)(1+y)}$. Due to (i) and (ii), we have that $x \ge 1$ and $y \ge 1$. In other words, we can upper bound the ratio $f'/f$ by the maximum of the function $g(x, y)$ with $x, y \ge 1$. It is easy to show that the function $g(x, y)$ is decreasing with both $x$ and $y$. Then its maximum is obtained for $x = y = 1$ and it is equal to 3/4, showing that $f' \le 3f/4$. $\square$

## 2.2 Separated by Two Parallel Lines

In this section, we prove the following theorem, which is a generalization of Theorem 1.

**Theorem 2.** Consider a multigraph $(P, S)$ with $P = C \cup T_1 \cup T_2$ where $C$ is in convex position and there exist two horizontal lines $l_1, l_2$, with $T_1$ above $l_1$ above $C$ above $l_2$ above $T_2$. Let $T = T_1 \cup T_2$, $n = |S|$, and $t$ be the number of $T$-segments. There exists an untangle sequence of length $\mathcal{O}(t|P| \log |C| + n \log |C|) = \mathcal{O}(tn \log n)$ using only insertion choice.

*Proof.* We start by describing the insertion choice for flips involving at least one point in $T$. Let $p_1, \dots, p_{|P|}$ be the points $P$ sorted vertically from top to bottom. Consider a flip involving the points $p_a, p_b, p_c, p_d$ with $a < b < c < d$. The insertion choice is to create the segments $p_a p_b$ and $p_c p_d$. As in [9], we define the potential $\eta$ of a segment $p_i p_j$ as $\eta(p_i p_j) = |i - j|$. Notice that $\eta$ is an integer between 1 and $|P| - 1$. We define $\eta_T(S)$ as the sum of $\eta(p_i p_j)$ for $p_i p_j \in S$ with $p_i$ or $p_j$ in $T$. Notice that $0 < \eta_T(S) < t|P|$. It is easy to verify that any flip involving a point in $T$ decreases $\eta_T(S)$ and other flips do not change $\eta_T(S)$. Hence, the number of flips involving at least one point in $T$ is $\mathcal{O}(t|P|)$.
For the flips involving only points of C, we use the same choice as in the proof of Theorem 1. The potential function

$$ \phi(S) = \prod_{p_i p_j \in S : p_i \in C \text{ and } p_j \in C} \delta(p_i p_j) $$

is at most $|C|^n$ and decreases by a factor of at most 3/4 at every flip that involves only points of C.

However, $\phi(S)$ may increase by a factor of $O(|C|^2)$ when performing a flip that involves a point in $T$. As such flips only happen $O(t|P|)$ times, the total increase is at most a factor of $|C|^{O(t|P|)}$.

Concluding, the number of flips involving only points in C is at most

$$ \log_{4/3} \left( |C|^{O(n)} |C|^{O(t|P|)} \right) = O(n \log |C| + t|P| \log |C|).\square $$

# 3 Removal Choice

In this section, we show how to untangle a multigraph using only removal choice. We start with the convex case, followed by 1 point inside or outside the convex hull of C, then 2 points outside the convex hull of C, 2 points inside the convex hull of C, and 1 point inside and 1 outside the convex hull of C. As only removal choice is used, all results also apply to red-blue matchings, TSP tours, and trees.

## 3.1 Convex

Let $P = C = \{p_1, \dots, p_{|C|}\}$ be a set of points in convex position sorted in counterclockwise order along the convex hull boundary and consider a set of segments $S$ with endpoints $P$. Given a segment $p_a p_b$ and assuming without loss of generality that $a < b$, we define the crossing depth $\delta_\times(p_a p_b)$ as the number of points in $p_{a+1}, \dots, p_{b-1}$ that are an endpoint of a segment in $S$ that crosses any other segment in $S$ (not necessarily $p_a p_b$). We use the crossing depth to prove the following theorem, which implies a simpler and more general proof of the $O(n \log n)$ bound for trees [7].

**Theorem 3.** Every multigraph $(C, S)$ with $C$ in convex position has an untangle sequence of length $O(n \log |C|) = O(n \log n)$ using only removal choice, where $n = |S|$.

*Proof.* We repeat the following procedure until there are no more crossings. Let $p_a p_b \in S$ be a segment with crossings (hence, crossing depth at least one) and $a < b$ minimizing $\delta_\times(p_a p_b)$ (Figure 3(a)). Let $q_1, \dots, q_{\delta_\times(p_a p_b)}$ be the points defining $\delta_\times(p_a p_b)$ in order and let $i = \lceil \delta_\times(p_a p_b)/2 \rceil$. Since $p_a p_b$ has minimum crossing depth, the point $q_i$ is the endpoint of segment $q_i p_c$ that crosses $p_a p_b$. When flipping $q_i p_c$ and $p_a p_b$, we obtain a segment $s$ (either $s = q_i p_a$ or $s = q_i p_b$) with $\delta_\times(s)$ at most half of the original value of $\delta_\times(p_a p_b)$ (Figure 3(b,c)). Hence, this operation always divides the value of the smallest positive crossing depth by
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Proof of Theorem 3. (a) The segments of a convex multigraph are labeled with the crossing depth. (b,c) Two possible pairs of inserted segments, with one segment of the pair having crossing depth ⌊$\frac{3}{2}$⌋ = 1.</figcaption></figure>

at least two. As the crossing depth is an integer smaller than |C|, after performing
this operation $O(\log |C|)$ times, it produces a segment of crossing depth 0. As
the segments of crossing depth 0 can no longer participate in a flip, the claimed
bound follows. □

**3.2 One Point Inside or Outside a Convex Region**

In this section, we prove Theorem 4. In the case of TSP tours [25,28] and red-blue matchings [8], the preprocessing to untangle *CC*-segments takes $O(n)$ flips. However, in the case of trees [8] and in general (Theorem 3), the best bound known is $O(n \log n)$. We first state a lemma used to prove Theorem 4.

**Lemma 3.** Consider a set *C* of points in convex position, and a multiset *S* of *n* crossing-free segments with endpoints in *C*. Consider the multiset *S* ∪ {s} where *s* is an extra segment with one endpoint in *C* and one endpoint *q* anywhere in the plane. There exists an untangle sequence for *S* ∪ {s} of length *O*(n) using only removal choice.

*Proof.* Iteratively flip the segment $qp_1$ with the segment $p_2p_3 \in S$ crossing $qp_1$ the farthest from *q*. This flip inserts a *CC*-segment $p_1p_2$, which is impossible to flip again, because the line $p_1p_2$ is crossing free. The flip does not create any crossing between *CC*-segments. $\square$

We are now ready to state and prove the theorem.

**Theorem 4.** Consider a multigraph (*P*, *S*) with *P* = *C* ∪ *T* where *C* is in convex position, where *T* = {*q*}, and such that there is no crossing pair of *CC*-segments (possibly after a preprocessing for the convex case). Let *n* = |*S*| and *t* be the number of *T*-segments. There exists an untangle sequence of length *O*(*tn*) using only removal choice.

*Proof.* For each segment *s* with endpoint *q* with crossing, we apply Lemma 3 to *s* and the *CC*-segments crossing *s*. Once a segment *s* incident to *q* is crossing free, it is impossible to flip it again as we fall in one of the following cases. Let *ℓ* be the line containing *s*.
**Case 1:** If $\ell$ is crossing free, then it splits the multigraph in three partitions: the segments on one side of $\ell$, the segments on the other side of $\ell$, and the segment $s$ itself.

**Case 2:** If $\ell$ is not crossing free and $q$ is outside the convex hull of $C$, then $s$ is *uncrossable*.

**Case 3:** If $q$ is inside the convex hull of $C$, then introducing a crossing on $s$ would require that $q$ lies in the interior of the convex quadrilateral whose diagonals are the two segments removed by a flip. The procedure excludes this possibility by ensuring that there are no crossing pair of CC-segments, and, therefore, that one of the removed segment already has $q$ as an endpoint.

Therefore, we need at most $n$ flips for each of the $t$ segments incident to $q$. $\square$

### 3.3 Two Points Not in Convex Position

In this section, we consider the case of two points that are not in convex position. We present the proof for a matching with two points outside a convex region. The remaining cases hold for general multigraphs but the proofs are long and technical. These proofs are presented in the full version.

**Theorem 5.** *Consider a matching $(P, S)$ with $P = C \cup T$ where $C$ is in convex position, where $T = \{q, q'\}$, and such that there is no crossing pair of CC-segments (possibly after a preprocessing for the convex case). Let $n = |S|$. There exists an untangle sequence of length $\mathcal{O}(n)$ using only removal choice.*

*Proof.* Throughout this proof, we partition the *TT*-segments respectively the *CT*-segments into two types: *TTI*-segments and *CTI*-segments if they intersect the interior of the convex hull of $C$ and *TTO*-segments and *CTO*-segments otherwise. Next, we describe the removal choices of an untangle sequence of a matching such as the one shown in Figure 4(a). We decompose this sequence into two phases.

**Phase 1:** *handle a TT-segment.* If the *TT*-segment $s = qq'$ is in $S$ and crosses no segment in $S$, then $S$ is crossing free. If the *TT*-segment $s = qq'$ is in $S$ and crosses at least one segment in $S$ (necessarily a *CC*-segment), then we flip $s = qq'$ with any segment, say $s'$. The line containing $s'$ now splits $S$ into one matching with $q$ and another matching with $q'$. Figures 4(b) and (c) show the splitting line in the two possible insertion cases. We untangle each of these two matchings using $\mathcal{O}(n)$ flips by Theorem 4. Figure 4(d) shows an example of the matching $S$ at the end of Phase 1.

**Phase 2:** *handle CT-segments.* We remove an arbitrary *CT*-segment $s$, say the segment incident to $q$, from $S$. We then untangle $S$ using $\mathcal{O}(n)$ flips by Theorem 4, and insert the segment $s$ back in $S$ afterwards. Notice that all crossings are now on $s$.

While $s'$, the segment of $S$ that crosses $s$ the farthest away from $q$, is a *CC*-segment, we flip $s$ and $s'$ and we set $s$ to be the newly inserted *CT*-segment incident to $q$. By Lemma 3, at most $\mathcal{O}(n)$ flips are performed in this loop.
<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Illustrations for the proof of Theorem 5. (a) Example of the matching *S* before Phase 1. (b) & (c) Illustration of the two insertion cases of Phase 1. In both insertion cases, the highlighted line splits the matching. (d) Example of the matching *S* before Phase 2. (e) & (f) & (g) The three sub-cases of Insertion case 1 of Phase 2. (h) Example of the Insertion case 2 of Phase 2.</figcaption></figure>

At the end of the loop, either *s* is crossing free, or *s'* is adjacent to *q'*. Then, we also flip *s* and *s'*.

**Insertion case 1:** If two *CT*-segments are inserted, then we examine the two following three cases.

If *s'* is a *CTI*-segment, then the line containing *s'* now splits *S* into one matching with *q* and another matching with *q'* (Figure 4(e)). Again, we untangle each of these two matchings using $O(n)$ flips by Theorem 4.

If *s'* is a *CTO*-segment and *s* is a *CTI*-segment, then *s'* is the only segment crossing *s* before the flip. Thus, after the flip, the line containing *s* splits *S* into one matching with *q* and another matching with *q'* (Figure 4(f)). Again, we untangle each of these two matchings using $O(n)$ flips by Theorem 4.

If both *s* and *s'* are *CTO*-segments, then *S* is crossing free after the flip (Figure 4(g)).

**Insertion case 2:** If the *TT*-segment *qq'* is inserted (Figure 4(h)), then we apply Phase 1 to untangle *S* using $O(n)$ flips.

In total, we have used $O(n)$ flips to untangle *S*.

<figure><img src="image_6.png" /></figure>

In the full version, we prove the following two theorems that handle the remaining cases of two points that are not in convex position.

**Theorem 6.** Consider a multigraph (*P*, *S*) with *P* = *C* ∪ *T* where *C* is in convex position, the points of *T* are inside the convex hull of *C*, and *T* = {*q*, *q'*}. Let
$n = |S|$ and $t$ be the number of $T$-segments. There exists an untangle sequence of length $\mathcal{O}(d_{\text{conv}}(n) + tn)$ using only removal choice, where $d_{\text{conv}}(n)$ is the number of flips to untangle any multiset of at most $n$ segments with endpoints in convex position.

*Proof.* (Sketch) The untangle sequence is decomposed in five phases. At the end of each phase, one more type of crossings is removed, and types of crossings removed in the previous phases are not present, even if they may temporarily appear during the phase. *Phase 1.* We untangle the *CT*-segments using $\mathcal{O}(d_{\text{conv}}(n))$ flips. *Phase 2.* We untangle the *CC*-segments using $\mathcal{O}(d_{\text{conv}}(n))$ flips. *Phase 3.* We remove the crossings between *CT*-segments and *CC*-segments that cross $qq'$ using $\mathcal{O}(tn)$ flips. *Phase 4.* We remove the remaining crossings between *CT*-segments and *CC*-segments using $\mathcal{O}(tn)$ flips. *Phase 5.* We remove the remaining crossings, which are between $qq'$ and *CC*-segments, using $\mathcal{O}(d_{\text{conv}}(n))$ flips. $\square$

**Theorem 7.** Consider a multigraph $(P, S)$ with $P = C \cup T$ where $C$ is in convex position, and $T = \{q, q'\}$ such that $q$ is outside the convex hull of $C$ and $q'$ is inside the convex hull of $C$. Let $n = |S|$ and $t$ be the number of $T$-segments. There exists an untangle sequence of length $\mathcal{O}(d_{\text{conv}}(n) + \delta(q)\delta(q')n) = \mathcal{O}(d_{\text{conv}}(n) + t^2n)$ using only removal choice, where $d_{\text{conv}}(n)$ is the number of flips to untangle any multiset of at most $n$ segments with endpoints in convex position.

*Proof.* (Sketch) The untangle sequence is decomposed in four phases. *Phase 1.* We untangle the *CC*-segments using $d_{\text{conv}}(n)$ flips. *Phase 2.* We remove the crossings between *Cq'-segments* and *CC-segments* using $\mathcal{O}(tn)$ flips (Theorem 4). *Phase 3.* We remove the crossings between *Cq-segments* using $\mathcal{O}(t^2n)$ flips. *Phase 4.* We remove the crossings between $qq'$ and *CC-segments*, using $\mathcal{O}(tn)$ flips. $\square$

# 4 Removal and Insertion Choices

In this section, we show how to untangle a matching or a multigraph using both removal and insertion choices. We start with the case of points outside the convex separated by two parallel lines. Afterwards, we prove an important lemma and apply it to untangle a matching with points outside the convex.

## 4.1 Separated by Two Parallel Lines

We start with the simpler case in which $T$ is separated from $C$ by two parallel lines. In this case, our bound of $\mathcal{O}(n + t|P|)$ interpolates the tight convex bound of $\mathcal{O}(n)$ from $[7]$ and the $\mathcal{O}(t|P|)$ bound from $[9]$ for $t$ arbitrary segments.

**Theorem 8.** Consider a multigraph $(P, S)$ with $P = C \cup T_1 \cup T_2$ where $C$ is in convex position and there exist two horizontal lines $l_1, l_2$, with $T_1$ above $l_1$ above $C$ above $l_2$ above $T_2$. Let $n = |S|$, $T = T_1 \cup T_2$, and $t$ be the number of $T$-segments. There exists an untangle sequence of length $\mathcal{O}(n + t|P|) = \mathcal{O}(tn)$ using both removal and insertion choices.
*Proof.* The algorithm runs in two phases.

**Phase 1.** We use removal choice to perform the flips involving a point in $T$. At the end of the first phase, there can only be crossings among segments with all endpoints in $C$. The insertion choice for the first phase is the following. Let $p_1, \dots, p_{|P|}$ be the points $P$ sorted vertically from top to bottom. Consider a flip involving the points $p_a, p_b, p_c, p_d$ with $a < b < c < d$. The insertion choice is to create the segments $p_a p_b$ and $p_c p_d$. As in $[9]$, we define the potential $\eta$ of a segment $p_i p_j$ as $\eta(p_i p_j) = |i - j|$. Notice that $\eta$ is an integer from 1 to $|P| - 1$. We define $\eta(S)$ as the sum of $\eta(p_i p_j)$ for $p_i p_j \in S$ with $p_i$ or $p_j$ in $T$. Notice that $0 < \eta(S) < t|P|$. It is easy to verify that any flip involving a point in $T$ decreases $\eta(S)$. Hence, the number of flips in Phase 1 is $\mathcal{O}(t|P|)$.

**Phase 2.** Since $T$ is outside the convex hull of $C$, flips between segments with all endpoints in $C$ cannot create crossings with the other segments, which are guaranteed to be crossing free at this point. Hence, it suffices to run an algorithm to untangle a convex set with removal and insertion choice from $[7]$, which performs $\mathcal{O}(n)$ flips. $\square$

## 4.2 Liberating a Line

In this section, we prove the following key lemma, which we use next. The lemma only applies to matchings and it is easy to find a counter-example for multisets ($S$ consisting of $n$ copies of a single segment that crosses $pq$).

**Lemma 4.** Consider a matching $S$ of $n$ segments with endpoints $C$ in convex position, and a segment $pq$ separating $C$. Using $\mathcal{O}(n)$ flips with removal and insertion choices on the initial set $S \cup \{pq\}$, we obtain a set of segments that do not cross the line $pq$.

*Proof.* For each flip performed in the subroutine described hereafter, at least one of the inserted segments does not cross the line $pq$ and is removed from $S$ (see Figure 5).

<figure><img src="image_7.png" /><figcaption>**Fig. 5.** An untangle sequence of the subroutine to liberate the line $pq$ (with $n = 4$).</figcaption></figure>

**Preprocessing.** First, we remove from $S$ the segments that do not intersect the line $pq$, as they are irrelevant. Second, anytime two segments in $S$ cross, we flip them choosing to insert the pair of segments not crossing the line $pq$. One
such flip removes two segments from $S$. Let $p_1p_2$ (respectively $p_{2n-1}p_{2n}$) be the segment in $S$ whose intersection point with $pq$ is the closest from $p$ (respectively $q$). Without loss of generality, assume that the points $p_1$ and $p_{2n-1}$ are on the same side of the line $pq$.

**First flip.** Elementary geometry yields that at least one of the segments among $pp_{2n-1}$, $qp_1$, $qp_2$ intersects all the segments of $S$ (see full version).

Without loss of generality, assume that $pp_{2n-1}$ is such a segment, i.e., that $pp_{2n-1}$ crosses all segments of $S \setminus \{p_{2n-1}p_{2n}\}$. We choose to remove the segments $pq$ and $p_{2n-1}p_{2n}$, and we choose to insert the segments $pp_{2n-1}$ and $qp_{2n}$. As the segment $qp_{2n}$ does not cross the line $pq$, we remove it from $S$.

**Second flip.** We choose to flip the segments $pp_{2n-1}$ and $p_1p_2$. If $n$ is odd, we choose to insert the pair of segments $pp_1, p_2p_{2n-1}$. If $n$ is even, we insert the segments $pp_2, p_1p_{2n-1}$.

By convexity, one of the inserted segment (the one with endpoints in $C$) crosses all other $n-2$ segments. The other inserted segment (the one with $p$ as one of its endpoints) does not cross the line $pq$, so we remove it from $S$. Note that the condition on the parity of $n$ is there only to ensure that the last segment $p_{2n-3}p_{2n-2}$ is dealt with at the last flip.

**Remaining flips.** We describe the third flip. The remaining flips are performed similarly. Let $s$ be the previously inserted segment. Let $p_3p_4$ be the segment in $S$ whose intersection point with $pq$ is the closest from $p$. Without loss of generality, assume that $p_3$ is on the same side of the line $pq$ as $p_1$ and $p_{2n-1}$.

We choose to flip $s$ with $p_3p_4$. If $s = p_2p_{2n-1}$, we choose to insert the pair of segments $p_2p_4, p_3p_{2n-1}$. If $s = p_1p_{2n-1}$, we choose to insert the pair of segments $p_1p_3, p_4p_{2n-1}$.

By convexity, one inserted segment (the one with $p_{2n-1}$ as an endpoint) crosses all other $n-3$ segments. The other inserted segment does not cross the line $pq$, so we remove it from $S$. Note that the insertion choice described is the only viable one, as the alternative would insert a crossing-free segment crossing the line $pq$ that cannot be removed. □

## 4.3 Points Outside a Convex Region

We are now ready to prove the following theorem, which only applies to matchings because it uses Lemma 4.

**Theorem 9.** Consider a matching $S$ consisting of $n$ segments with endpoints $P = C \cup T$ where $C$ is in convex position and $T$ is outside the convex hull of $C$. Let $t = |T|$. There exists an untangle sequence of length $O(t^3n)$ using both removal and insertion choices.

*Proof.* Throughout this proof, we partition the *TT*-segments into two types: *TTI*-segment if it intersects the interior of the convex hull of $C$ and *TTO*-segment otherwise.

**TT-segments.** At any time during the untangle procedure, if there is a *TTI*-segment $s$ that crosses more than $t$ segments, we apply Lemma 4 to liberate $s$.
from every *CC*-segment using $O(n)$ flips. Let $\ell$ be the line containing $s$. Since $\lambda(\ell)$
cannot increase (Lemma 1), $\lambda(\ell) < t$ after Lemma 4, and there are $O(t^2)$ different
*TTI*-segments, it follows that Lemma 4 is applied $O(t^2)$ times, performing a total
$O(t^2n)$ flips. As the number of times $s$ is inserted and removed differ by at most
1 and $\lambda(\ell)$ decreases at each flip that removes $s$, it follows that $s$ participates in
$O(t)$ flips. As there are $O(t^2)$ different *TTI*-segments, the total number of flips
involving *TTI*-segments is $O(t^3)$.

We define a set $L$ of $O(t)$ lines as follows. For each point $q \in T$, we have
two lines $\ell_1, \ell_2 \in L$ that are the two tangents of the convex hull of $C$ that pass
through $q$. As the lines $\ell \in L$ do not separate $C$, the potential $\lambda(\ell) = O(t)$. When
flipping a *TTO*-segment $q_1q_2$ with another segment $q_3p$ with $q_3 \in T$ ($p$ may be
in $T$ or in $C$), we make the insertion choice of creating a *TTO*-segment $q_1q_3$
such that there exists a line $\ell \in L$ whose potential $\lambda(\ell)$ decreases. It is easy to
verify that $\ell$ always exist (see full version). Hence, the number of flips involving
*TTO*-segments is $O(t^2)$ and the number of flips involving *TT*-segments in general
is $O(t^3)$.

**All except pairs of CC-segments.** We keep flipping segments that are not both CC-segments with the following insertion choices. Whenever we flip two CT-segments, we make the insertion choice of creating a TT-segment. Hence, as the number of flips involving TT-segments is $O(t^3)$, so is the number of flips of two CT-segments.

Whenever we flip a *CT*-segment $p_1q$ with $q \in T$ and a *CC*-segment $p_3p_4$,
we make the following insertion choice. Let $v(q)$ be a vector such that the dot
product $v(q) \cdot q < v(q) \cdot p$ for all $p \in C$, that is, $v$ is orthogonal to a line $\ell$
separating $q$ from $C$ and pointing towards $C$. We define the potential $\eta(p_xq)$
of a segment with $p_x \in C$ and $q \in T$ as the number of points $p \in C$ such that
$v(q) \cdot p < v(q) \cdot p_x$, that is the number of points in $C$ before $p_x$ in direction $v$. We
choose to insert the segment $p_xq$ that minimizes $\eta(p_xq)$ for $x = \{1, 2\}$. Let $\eta(S)$
be the sum of $\eta(p_xq)$ for all *CT*-segments $p_xq$ in $S$. It is easy to see that $\eta(S)$
is $O(t|C|)$ and decreases at each flip involving a *CT*-segment (not counting the
flips inside Lemma 4).

There are two situation in which $\eta(S)$ may increase. One is when Lemma 4
is applied, which happens $O(t^2)$ times. Another one is when a *TT*-segment and
a *CC*-segment flip, creating two *CT*-segments, which happens $O(t^3)$ times. At
each of these two situations, $\eta(S)$ increases by $O(|C|)$. Consequently, the number
of flips between a *CT*-segment and a *CC*-segment is $O(t^3|C|) = O(t^3n)$.

**CC-segments.** By removal choice, we choose to flip the pairs of *CC*-segments last (except for the ones flipped in Lemma 4). As *T* is outside the convex hull of *C*, flipping two *CC*-segments does not create crossings with other segments (Lemma 2). Hence, we apply the algorithm from [7] to untangle the remaining segments using $O(n)$ flips. □

References

1. Aichholzer, O., Ballinger, B., Biedl, T., Damian, M., Demaine, E.D., Korman, M., Lubiw, A., Lynch, J., Tkadlec, J., Uno, Y.: Reconfiguration of non-crossing
spanning trees. arXiv preprint (2022), https://arxiv.org/abs/2206.03879

2. Aichholzer, O., Knorr, K., Löffler, M., Masárová, Z., Mulzer, W., Obenaus, J., Paul, R., Vogtenhuber, B.: Flipping plane spanning paths. In: International Conference and Workshops on Algorithms and Computation (WALCOM) (2023). https://doi.org/10.1007/978-3-031-27051-2_5, https://arxiv.org/abs/2202.10831

3. Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is NP-complete. Discrete & Computational Geometry 54(2), 368–389 (2015). https://doi.org/10.1007/s00454-015-9709-7

4. Akl, S.G., Islam, M.K., Meijer, H.: On planar path transformation. Information processing letters 104(2), 59–64 (2007). https://doi.org/10.1016/j.ipl.2007.05.009

5. Bereg, S., Ito, H.: Transforming graphs with the same degree sequence. In: Computational Geometry and Graph Theory. pp. 25–32 (2008). https://doi.org/10.1007/978-3-540-89550-3_3

6. Bereg, S., Ito, H.: Transforming graphs with the same graphic sequence. Journal of Information Processing 25, 627–633 (2017). https://doi.org/10.2197/ipsjjip.25.627

7. Biniaz, A., Maheshwari, A., Smid, M.: Flip distance to some plane configurations. Computational Geometry 81, 12–21 (2019). https://doi.org/10.1016/j.comgeo.2019.01.008, https://arxiv.org/abs/1905.00791

8. Bonamy, M., Bousquet, N., Heinrich, M., Ito, T., Kobayashi, Y., Mary, A., Mühlenphaler, M., Wasa, K.: The perfect matching reconfiguration problem. In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS). LIPIcs, vol. 138, pp. 80:1–80:14 (2019). https://doi.org/10.4230/LIPIcs.MFCS.2019.80

9. Bonnet, É., Miltzow, T.: Flip distance to a non-crossing perfect matching. arXiv 1601.05989 (2016), http://arxiv.org/abs/1601.05989

10. Bousquet, N., Joffard, A.: Approximating shortest connected graph transformation for trees. In: Theory and Practice of Computer Science. pp. 76–87 (2020). https://doi.org/10.1007/978-3-030-38919-2_7

11. 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/10.1016/j.ipl.2008.12.017

12. Das, A.K., Das, S., da Fonseca, G.D., Gerard, Y., Rivier, B.: Complexity results on untangling red-blue matchings. Computational Geometry 111, 101974 (2023). https://doi.org/10.1016/j.comgeo.2022.101974, https://arxiv.org/abs/2202.11857

13. Englert, M., Röglin, H., Vöcking, B.: Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica 68(1), 190–264 (2014). https://doi.org/10.1007/s00453-013-9801-4

14. Erdős, P.L., Király, Z., Miklós, I.: On the swap-distances of different realizations of a graphical degree sequence. Combinatorics, Probability and Computing 22(3), 366–383 (2013). https://doi.org/10.1017/S0963548313000096

15. da Fonseca, G.D., Gerard, Y., Rivier, B.: On the longest flip sequence to untangle segments in the plane. In: International Conference and Workshops on Algorithms and Computation (WALCOM 2023). Lecture Notes in Computer Science, vol. 13973, pp. 102–112 (2023). https://doi.org/10.1007/978-3-031-27051-2_10, https://arxiv.org/abs/2210.12036

16. Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph. I. Journal of the Society for Industrial and Applied Mathematics 10(3), 496–506 (1962)

17. Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph II. uniqueness. Journal of the Society for Industrial and Applied Mathematics 11(1), 135–147 (1963)
16 G. D. da Fonseca, Y. Gerard, and B. Rivier

18. van den Heuvel, J.: The complexity of change. Surveys in Combinatorics 409, 127–160 (2013)

19. Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations. Discrete & Computational Geometry 22(3), 333–346 (1999)

20. Joffard, A.: Graph domination and reconfiguration problems. Ph.D. thesis, Université Claude Bernard Lyon 1 (2020)

21. Lawson, C.L.: Transforming triangulations. Discrete Mathematics 3(4), 365–372 (1972)

22. van Leeuwen, J., Schoone, A.A.: Untangling a traveling salesman tour in the plane. In: 7th Workshop on Graph-Theoretic Concepts in Computer Science (1981)

23. Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point set is NP-complete. Computational Geometry 49, 17–23 (2015). https://doi.org/10.1016/j.comgeo.2014.11.001

24. Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4) (2018). https://doi.org/10.3390/a11040052

25. Oda, Y., Watanabe, M.: The number of flips required to obtain non-crossing convex cycles. In: Kyoto International Conference on Computational Geometry and Graph Theory. pp. 155–165 (2007)

26. Pilz, A.: Flip distance between triangulations of a planar point set is APX-hard. Computational Geometry 47(5), 589–604 (2014). https://doi.org/10.1016/j.comgeo.2014.01.001

27. Will, T.G.: Switching distance between graphs with the same degrees. SIAM Journal on Discrete Mathematics 12(3), 298–306 (1999). https://doi.org/10.1137/S0895480197331156

28. Wu, R., Chang, J., Lin, J.: On the maximum switching number to obtain non-crossing convex cycles. In: 26th Workshop on Combinatorial Mathematics and Computation Theory. pp. 266–273 (2009)