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)

IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria www.ist.ac.at © IST 2020