2005/09/30 by Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Computational Geometry and Mesh Generation #cs.CG #math.CO #msc:05C10
paper · pdf · doi:10.1002/jgt.20214
published as J. Graph Theory 54(4):307-330, 2007 · A short version of this paper will be presented at SODA 2006
arxiv created 2006/04/26 · openalex publication_date 2006/12/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \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\over3(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\over7(n-2) edges. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 307–330, 2007