Connectivity of triangulation flip graphs in the plane (Q2105329)

Let \(P\) be a finite planar point set in general position and let \(\mathcal{T}_{\mathrm{full}}(P)\), \(\mathcal{T}_{\mathrm{part}}(P)\) and \(\mathcal{T}_{\mathrm{reg}}(P)\) be the sets of all full, partial and regular triangulations of \(P\). In the paper under review, the authors study the graphs whose vertex sets are the aforementioned set of triangulations and whose adjacency relations are determined by local operations that transform one triangulation into another, known as edge flip, point insertion flip, and point removal flip. The resulting graphs are the so-called edge flip graphs and bistellar flip graphs. It is well known (see [\textit{C. L. Lawson}, Discrete Math. 3, 365--372 (1972; Zbl 0253.05116)]) that (two of) these graphs are connected. The analysis of the authors goes deeper by studying in detail the structure of these graphs with particular regard to their vertex connectivity. As major results of the paper, the authors determine the vertex connectivity of the edge flip graph and the bistellar flip graph, extending the result to the subgraph of the edge flip graph induced by the regular triangulations of \(P\). Inspired by works of \textit{I. M. Gel'fand} et al. [Sov. Math., Dokl. Akad. Nauk SSSR 308, No. 1, 20--23 (1989; Zbl 0742.14042)] and \textit{M. L. Balinski} [Pac. J. Math. 11, 431--434 (1961; Zbl 0103.39602)] where the authors studied polytopes associated with a planar set of points in general position (the associahedron when \(P\) is in convex position and the secondary polytope), Wagner and Weil develop a sophisticated method by proving first that the edge flip graph and the bistellar flip graph can be covered by graphs associated to the product of associahedron and to products of secondary polytopes. All the vertex connectivity bounds are proved using a local variant of Menger's theorem, that assures, assuming connectedness, the \(k\)-vertex connectivity if there exist \(k\) internally vertex-disjoint paths between any two vertices at distance 2. By considering the natural partial order on the sets of full and partial subdivisions of \(P\), they also give two independent conditions for a partial triangulation to be regular, one only sufficient, the other also necessary, providing explicit examples of triangulations that do not satisfy these conditions. Finally, the authors also prove, unlike the higher dimension case, the existence of arbitrarily large sets of points in general position \(P\) with nonregular partial triangulations and such that any proper subset of \(P\) has only regular triangulations.