Connectivity of triangulation flip graphs in the plane

DOI10.1007/S00454-022-00436-2MaRDI QIDQ2105329zbMATH OpenOpenAlexFDO

Publication date 8 December 2022

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2003.13557

bistellar flip graph graph connectivity Menger's theorem regular triangulation secondary polytope simultaneously flippable edges

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Combinatorial complexity of geometric structures (52C45) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

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.

Recommendations

Cites work

Cited in

(23)

This page was built for publication: Connectivity of triangulation flip graphs in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2105329)