  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.
