Flip Graphs of Pseudo-Triangulations With Face Degree at Most 4

A pseudo-triangle is a simple polygon with exactly three convex vertices, and all other vertices (if any) are distributed on three concave chains. A pseudo-triangulation~T of a point set~P in~R² is a partitioning of the convex hull of~P into pseudo-triangles, such that the union of the vertices of the pseudo-triangles is exactly~P. We call a size-4 pseudo-triangle a dart. For a fixed k≥ 1, we study k-dart pseudo-triangulations (k-DPTs), that is, pseudo-triangulations in which exactly k faces are darts and all other faces are triangles. We study the flip graph for such pseudo-triangulations, in which a flip exchanges the diagonals of a pseudo-quadrilatral. Our results are as follows. We prove that the flip graph of $1$-DPTs is generally not connected, and show how to compute its connected components. Furthermore, for k-DPTs on a point configuration called the double chain we analyze the structure of the flip graph on a more fine-grained level.