Oswin Aichholzer, Thomas Hackl, Davíd Orden, Pedro Ramos, Günter
Rote, André Schulz, and Bettina Speckmann:
Flip graphs of boundeddegree triangulations

In: European Conference on Combinatorics, Graph Theory and Applications
(EuroComb 2009), Bordeaux, September 2009, Editors: Jaroslav Nešetřil and
André Raspaud, Electronic
Notes in Discrete Mathematics
34 (2009), 509–513.
doi:10.1016/j.endm.2009.07.084

Graphs and Combinatorics 29 (2013), 1577–1593.
doi:10.1007/s0037301212290
arXiv:0903.2184
[math.CO].
Abstract
We study flip graphs of (pseudo)triangulations whose maximum vertex degree is
bounded by a constant k. In particular, we consider triangulations
of sets of n points in convex position in the plane and prove
that their flip graph is connected if and only if k>6; the
diameter of the flip graph is O(n^{2}). We also show that for general
point sets, flip graphs of pointed pseudotriangulations can be disconnected
for k<10, and flip graphs of triangulations can be disconnected for
any k.
Last update: August 15, 2017.