Flip Graphs of Pseudo-Triangulations With Face Degree at Most 4
<|reference_start|>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~$\mathcal{T}$ of a point set~$P$ in~$\mathbb{R}^2$ 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\geq 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.<|reference_end|>
@article{löffler2024flip,
    title={Flip Graphs of Pseudo-Triangulations With Face Degree at Most 4},
    author={Maarten L"offler, Tamara Mchedlidze, David Orden, Josef Tkadlec,
  Jules Wulms},
    journal={arXiv preprint arXiv:2402.12357},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.12357},
    primaryClass={cs.CG}
}