| Flip Graphs of Degree-Bounded (Pseudo-)Triangulations (2009) | |||||||||
Abstract | |||||||||
| We study flip graphs of (pseudo-)triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider (pseudo-)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 minimum pseudo-triangulations can be disconnected for k < 10, and flip graphs of triangulations can be disconnected for any k.. Comment: 9 pages, 12 figures | |||||||||
Publication details | |||||||||
| |||||||||