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 on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge  , removes a non-extreme point of degree 3, or adds a point in P \setminus P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices ; a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph , with emphasis on  connectivity. For sets P of n points in  general position, we show that the bistellar flip graph is ( n-3 )-connected, answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos). This matches the situation for regular triangulations ( partial triangulations obtained by lifting the points and projecting the lower convex hull ), where (n-3)-connectivity has been known since the 1980s via the secondary polytope ( Gelfand, Kapranov , Zelevinsky ) and Balinski's Theorem. Our methods yield further results for regular triangulations. Among others, we show that there are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction) .
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 .
D
on P
D
either
A
(an edge flip)
R
\setminus
\
R
;
, and
R
goal of this paper
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
R
the structure of this graph
these graphs
A
vertex
D
P
A
the plane in
R
bistellar
edge
R
n-3
n/2-2
R
answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos). This
and the bistellar flip graph is (n-3)-connected; both results are tight. The latter bound
R
regular triangulations (
the subfamily of regular triangulations, ie.
R
and projecting
to 3-space and projecting back
R
), where
. Here
R
1980s
late 80s
R
(
due to
R
, Zelevinsky )
Zelevinsky
R
Our methods yield further results for regular triangulations. Among others, we show that there are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction)
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