Triangulation Flip Graphs of Planar Point Sets

Abstract: Full triangulations of a finite planar point set P are maximal straight-line embedded plane graphs on P. In partial triangulations some non-extreme points can be skipped. Flips are minimal changes in triangulations. They define an adjacency relation on the set of triangulations of P, giving rise to the flip graph of all (full or partial) triangulations of P. In the seventies Lawson showed that flip graphs are always connected. Our goal is to investigate the structure of flip graphs, with emphasis on their vertex-connectivity. We obtain similar bounds as they follow for regular triangulations from secondary polytopes via Balinski’s Theorem. Joint work with Uli Wagner, IST Austria

computational geometrydiscrete mathematicsdata structures and algorithmscombinatorics

Audience: researchers in the discipline

Discrete and Computational Geometry Seminar in Paris

Series comments: Language is English if anyone in the audience prefers it (otherwise French).

Links and passwords for the talks are on the seminar homepage: monge.univ-mlv.fr/~hubard/GAC/