Open Collections

Bistellar and Edge Flip Graphs of Triangulations in the Plane - Geometry and Connectivity.

Banff International Research Station for Mathematical Innovation and Discovery

The set of all triangulations of a finite point set in the plane attains structure via flips: The graph, where two triangulations are adjacent if one can be obtained from the other by an elementary flip. This is an edge flip for full triangulations, or a bistellar flip for partial triangulations (where non-extreme points can be skipped). It is well-known (Lawson, 1972) that both, the edge flip graph and the bistellar flip graph are connected. For n the number of points and general position assumed, we show that the edge flip graph is (n/2 - 2)-connected and the bistellar flip graph is (n-3)-connected. Both bounds are tight. This matches the situation for regular triangulations (a subset of the partial triangulations), where (n-3)-connectivity was known through the secondary polytope (Gelfand, Kapranov, Zelevinsky, 1990) and Balinski's Theorem. We show that the edge flip graph can be covered by 1-skeletons of polytopes of dimension at least n/2-2 (products of associahedra). Similarly, the bistellar flip graph can be covered by 1-skeletons of polytopes of dimension at least n-3 (products of secondary polytopes). (covers joint research with Uli Wagner, IST Austria)

Mathematics; Geometry; Convex and discrete geometry; Discrete mathematics

video/mp4

Author affiliation: ETH Zurich

2020-04-09

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73954

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/