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

Flip graphs of bounded-degree triangulations

1. 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
2. Graphs and Combinatorics 29 (2013), 1577–1593. doi:10.1007/s00373-012-1229-0 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²). 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 any k.