Earlier Version

# Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)

Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841.

Conference Paper | Published | English

Scopus indexed
Author
Wagner, UliISTA ; Welzl, Emo
Department
Abstract
In a straight-line embedded triangulation of a point set P in the plane, removing an inner edge and—provided the resulting quadrilateral is convex—adding the other diagonal is called an edge flip. The (edge) flip graph has all triangulations as vertices, and a pair of triangulations is adjacent if they can be obtained from each other by an edge flip. The goal of this paper is to contribute to a better understanding of the flip graph, with an emphasis on its connectivity. For sets in general position, it is known that every triangulation allows at least edge flips (a tight bound) which gives the minimum degree of any flip graph for n points. We show that for every point set P in general position, the flip graph is at least -vertex connected. Somewhat more strongly, we show that the vertex connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P, provided P is large enough. Finally, we exhibit some of the geometry of the flip graph by showing that the flip graph can be covered by 1-skeletons of polytopes of dimension (products of associahedra). A corresponding result ((n – 3)-vertex connectedness) can be shown for the bistellar flip graph of partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. This will be treated separately in a second part.
Publishing Year
Date Published
2020-01-01
Proceedings Title
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume
2020-January
Page
2823-2841
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
Salt Lake City, UT, United States
Conference Date
2020-01-05 – 2020-01-08
ISBN
IST-REx-ID

### Cite this

Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2020-January. SIAM; 2020:2823-2841. doi:10.1137/1.9781611975994.172
Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2020–January, pp. 2823–2841). Salt Lake City, UT, United States: SIAM. https://doi.org/10.1137/1.9781611975994.172
Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2020–January:2823–41. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.172.
U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part I: Edge flips),” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 2823–2841.
Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841.
Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:10.1137/1.9781611975994.172.
All files available under the following license(s):
This Item is protected by copyright and/or related rights. [...]

Access Level
Open Access
Material in ISTA:
Later Version

### Export

Marked Publications

Open Data ISTA Research Explorer

arXiv 2003.13557