Premium
Simultaneous diagonal flips in plane triangulations
Author(s) -
Bose Prosenjit,
Czyzowicz Jurek,
Gao Zhicheng,
Morin Pat,
Wood David R.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20214
Subject(s) - combinatorics , diagonal , mathematics , triangulation , vertex (graph theory) , plane (geometry) , graph , geometry
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