Wagner, Uli ;
Welzl, Emo
Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)
Abstract
Given a finite point set P in general position in the plane, a full triangulation is a maximal straightline embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a nonextreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity.
For sets P of n points in general position, we show that the bistellar flip graph is (n3)connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n3)connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem.
Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with nonregular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of nonregular partial triangulations (answering a question by F. Santos in the unexpected direction).
BibTeX  Entry
@InProceedings{wagner_et_al:LIPIcs:2020:12225,
author = {Uli Wagner and Emo Welzl},
title = {{Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {67:167:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12225},
URN = {urn:nbn:de:0030drops122259},
doi = {10.4230/LIPIcs.SoCG.2020.67},
annote = {Keywords: triangulation, flip graph, graph connectivity, associahedron, subdivision, convex decomposition, flippable edge, flip complex, regular triangulation, bistellar flip graph, secondary polytope, polyhedral subdivision}
}
08.06.2020
Keywords: 

triangulation, flip graph, graph connectivity, associahedron, subdivision, convex decomposition, flippable edge, flip complex, regular triangulation, bistellar flip graph, secondary polytope, polyhedral subdivision 
Seminar: 

36th International Symposium on Computational Geometry (SoCG 2020)

Issue date: 

2020 
Date of publication: 

08.06.2020 