Simultaneous diagonal flips in plane triangulations

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 $\cal O$ ( 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 $\cal O$ (log n ) 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 $\cal O$ ( 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}\over{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}\over{7}}({n}-{2})$ edges. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 307–330, 2007