# Triangulation Flip Graphs of Planar Point Sets

## Emo Welzl, ETH Zürich

## Date and time: 2pm (New York time), Tuesday, November 10, 2020

## Place: On Zoom (details provided on the seminar mailing list)

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.