Please note: This master’s thesis presentation will take place online.
Reza Bigdeli, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Anna Lubiw
The flip graph for a set $P$ of points in the plane has a vertex for every triangulation of $P$, and an edge when two triangulations differ by one flip that replaces one triangulation edge by another.
The flip graph is known to have some connectivity properties:
- the flip graph is connected;
- connectivity still holds when restricted to triangulations containing some constrained edges between the points;
- for $P$ in general position of size $n$, the flip graph is $\lceil \frac{n}{2} -2 \rceil$-connected, a recent result of Wagner and Welzl (SODA 2020).
We introduce the study of connectivity properties of the flip graph when some edges between points are forbidden. An edge $e$ between two points is a flip cut edge if eliminating triangulations containing $e$ results in a disconnected flip graph. More generally, a set $X$ of edges between points of $P$ is a flip cut set if eliminating all triangulations that contain edges of $X$ results in a disconnected flip graph. The flip cut number of $P$ is the minimum size of a flip cut set.
We give a characterization of flip cut edges that leads to an $O(n \log n)$ time algorithm to test if an edge is a flip cut edge and, with that as preprocessing, an $O(n)$ time algorithm to test if two triangulations are in the same connected component of the flip graph. For a set of $n$ points in convex position (whose flip graph is the 1-skeleton of the associahedron) we prove that the flip cut number is $n-3$.