Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with n ≥ 6 vertices has a simultaneous flip into a 4-connected triangulation, and that the set of edges to be flipped can be computed in Ο(n) time. It follows that every triangulation has a simultaneous flip into a Hamiltonian triangulation. This result is used to prove that for any two n-vertex triangulations, there exists a sequence of Ο(logn) simultaneous flips to transform one into the other. Moreover, Ω(log n) simultaneous flips are needed for some pairs of triangulations. The total number of edges flipped in this sequence is Ο(n). The maximum size of a simultaneous flip is then studied. It is proved that every triangulation has a simultaneous flip of at least 1/3(n -2) edges. On the other hand, every simultaneous flip has at most n -2 edges, and there exist triangulations with a maximum simultaneous flip of 6/7(n - 2) edges.

Additional Metadata
Keywords Diagonal flip, Graph, Hamiltonian, Plane triangulation, Simultaneous flip
Persistent URL dx.doi.org/10.1002/jgt.20214
Journal Journal of Graph Theory
Citation
Bose, P, Czyzowicz, J. (Jurek), Gao, Z, Morin, P, & Wood, D. (2007). Simultaneous diagonal flips in plane triangulations. Journal of Graph Theory, 54(4), 307–330. doi:10.1002/jgt.20214