Flip graphs of bounded degree triangulations (Q2637710)

The flip graph of triangulations of a planar point is known to be connected. This text studies several subgraphs of this graph, where the vertex degree is bounded. First, it is proved that the subgraph of triangulations with vertex degree bounded by \(k\) is connected for any planar point set if, and only if, \(k>6\), and that the diameter of this subgraph is \(O(n^2)\). If the point set is not planar, it is proved the flip graph of pointed pseudo-triangulations can be disconnected if \(k\leq 9\), and the flip graph of triangulation can be disconnected for any \(k\). Finally, when the point set is convex, it is shown that two triangulations with maximal vertex degree \(k\) can be related in the flip graph by a path of triangulations of maximal vertex degree \(k+4\) of length \(O(n \ln(n))\).