Given a finite point set $P$ in general position in the plane, a full triangulation of $P$ is a maximal straight-line embedded plane graph on $P$. In a partial triangulation some non-extreme points can be skipped, i.e., it is a full triangulation of some subset $P'$ of $P$ containing all extreme points in $P$. Flips in triangulations are minimal changes: (i) removal of an edge and replacing it by another edge, or (ii) removal of an inner point of degree 3, or (iii) insertion of a skipped point and connecting it to the three vertices of the triangle where it lands in. These flips define an adjacency relation on the set of triangulations of the given set $P$, resulting in the edge flip graph of full triangulations and the bistellar flip graph of partial triangulations. In the early seventies Lawson showed that triangulation flip graphs are always connected.
Our goal is to investigate the structure of these graphs, with emphasis on their vertex connectivity.
For $n:=|P|$, we show that the edge flip graph is $\lceil \frac{n}{2}-2\rceil$-vertex connected, and the bistellar flip graph is $(n-3)$-vertex connected; both results are tight and resolve, for sets in general position, a question asked in the Triangulations book by De Loera, Rambau, and Santos. The bound for partial triangulations matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where $(n-3)$-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, and Zelevinsky (via Balinski's Theorem).
Joint work with Uli Wagner, IST Austria.