BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: In a straight line embedded triangulation of a point set P in
the plane\, removing an inner edge and - provided the resulting quadrilater
al Q is convex - adding the other diagonal is called an edge flip. The flip
graph has all triangulations as vertices and a pair of triangulations is a
djacent\, if they can be obtained from each other by an edge flip. This pre
sentation is towards a better understanding of this graph\, with emphasis o
n its connectivity. It is known that every triangulation allows at least
n/2-2 edge flips and we show (n/2-2)-vertex connectivity for flip graphs of
all P in general position\, n:=|P|. Somewhat stronger\, but restricted to
P large enough\, we show that the vertex connectivity is determined by the
minimum degree occurring in the flip graph\, i.e. the minimum number of fli
ppable edges in any triangulation of P. A corresponding result is shown
for so-called partial triangulations\, i.e. the set of all triangulations o
f subsets of P which contain all extreme points of P. Here the flip operati
on is extended to bistellar flips (edge flip\, and insertion and removal of
an inner vertex of degree three). We prove (n-3)-edge connectedness for al
l P in general position and (n-3)-vertex connectedness for n large enough (
(n-3) is tight\, since there is always a partial triangulation which allows
exactly n-3 bistellar flips). This matches the situation known (through th
e secondary polytope) for regular triangulations (i.e. partial triangulatio
ns obtained by lifting the points and projecting the lower convex hull).
This is joint work with Uli Wagner\, IST Austria.
DTSTAMP:20190424T133200
DTSTART:20190624T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Emo Welzl (ETH Zürich): Connectivity of Triangulation Flip Graphs i
n the Plane
UID:95691187@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20190624-L-Welzl.html
END:VEVENT
END:VCALENDAR