Flip graphs of bounded-degree triangulations

We study ¿ip graphs of 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 ¿ip graph is connected if and only if k > 6; the diameter of the ¿ip graph is O(n2). We also show that, for general point sets, ¿ip graphs of pointed pseudo-triangulations can be disconnected for k = 9, and ¿ip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the ¿ip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4. Keywords: Flip graphs - Triangulations - Rotation distance - Connectivity - Degree bound