20070401
Simultaneous diagonal flips in plane triangulations
Publication
Publication
Journal of Graph Theory , Volume 54  Issue 4 p. 307 330
Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with n ≥ 6 vertices has a simultaneous flip into a 4connected 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 nvertex 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  

, , , ,  
doi.org/10.1002/jgt.20214  
Journal of Graph Theory  
Organisation  School of Computer Science 
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
