Simultaneous diagonal flips in plane triangulations

Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

Abstract

Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with at least six vertices has a simultaneous flip into a 4-connected triangulation, and that it can be computed in linear 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 Ο(log n) simultaneous flips to transform one into the other. 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.
Original languageEnglish
Title of host publicationProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Pages212-221
Number of pages10
DOIs
Publication statusPublished - 2006
Externally publishedYes

Cite this