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