Oswin Aichholzer, Thomas Hackl, Davíd Orden, Pedro Ramos, Günter
Rote, André Schulz, and Bettina Speckmann:
Flip graphs of bounded-degree 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.
Graphs and Combinatorics 29 (2013), 1577–1593.
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(n2). We also show that for general
point sets, flip graphs of pointed pseudo-triangulations can be disconnected
for k<10, and flip graphs of triangulations can be disconnected for
Last update: August 15, 2017.