Connectivity of Triangulation Flip Graphs in the Plane

Area of Science:

• Computational Geometry
• Graph Theory
• Combinatorial Optimization

Background:

• Introduces full and partial triangulations of point sets in general position.
• Defines bistellar flips and the associated bistellar flip graph and edge flip graph.
• References prior work on the connectivity of these graphs.

Purpose of the Study:

• To investigate the structure of bistellar and edge flip graphs, focusing on vertex connectivity.
• To establish tight bounds for the vertex connectivity of these graphs for point sets of size n.
• To explore the relationship between triangulations, polytopes, and regularity.

Main Methods:

• Analysis of vertex connectivity for edge flip graphs and bistellar flip graphs.
• Utilizes concepts from polytope theory, including associahedra and secondary polytopes.
• Investigates the Hasse diagram of partial orders of partial subdivisions.

Main Results:

• The edge flip graph is shown to be (n-2)-vertex-connected, and the bistellar flip graph is (n-3)-vertex-connected, with both bounds being tight.
• Vertex connectivity of the edge flip graph is equal to the minimum degree for sufficiently large n.
• Demonstrates that these flip graphs can be covered by graphs of specific polytopes and analyzes conditions for regularity of partial triangulations.

Conclusions:

• Establishes new tight bounds for the vertex connectivity of fundamental triangulation graphs.
• Provides insights into the combinatorial structure of triangulations and their connection to geometric objects.
• Highlights the existence of non-regular triangulations and the complexity of their certificates.