Simultaneous diagonal flips in plane triangulations

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

Research output: Contribution to journalArticleResearchpeer-review

16 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)307-330
Number of pages24
JournalJournal of Graph Theory
Volume54
Issue number4
DOIs
Publication statusPublished - 2007
Externally publishedYes

Cite this