Paper detail

Connectivity of Triangulation Flip Graphs in the Plane

Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation flips an edge (an edge flip), removes a non-extreme point of degree 3, or adds a point in P \ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early 70s that these graphs are connected. Our goal is to investigate these graphs, with emphasis on vertex connectivity. For sets of n points in the plane in general position, we show that the edge flip graph is (n/2-2)-connected, and the bistellar flip graph is (n-3)-connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations, ie. partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull. Here (n-3)-connectivity has been known since the late 80s via the secondary polytope due to Gelfand, Kapranov & Zelevinsky and Balinski's Theorem. For the edge flip-graphs, the vertex connectivity can be shown to be at least as large as (and hence equal to) the minimum degree, provided n is large enough. Our methods yield several other results.