GeomTop Seminar: Connectivity of the Flip-Graph of Triangulations

---

We investigate the connectivity of the flip-graph of all (full )
triangulations of a given finite planar point set P in general position
and prove that, for n:=|P| large enough, both edge- and
vertex-connectivity are determined by the minimum degree occurring in
the flip-graph, i.e. the minimum number of flippable edges in any
triangulation of P. It is known that every triangulation allows at least
(n-4)/2 edge-flips.

This result is extended to so-called subtriangulations, i.e. the set of
all triangulations of subsets of P which contain all extreme points of
P, where the flip operation is extended to bistellar flips (edge-flips,
and insertion and removal of an inner vertex of degree three). Here we
prove (n-3)-edge-connectedness (for all P) and
(n-3)-vertex-connectedness of n large enough ((n-3) is tight, since
there is always a subtriangulation which allows exactly $n-3$ bistellar
flips). This matches the situation known (through the secondary
polytope) for so-called regular triangulations.

(joint work with Uli Wagner, IST Austria)

---

Download ICS Download invitation