Simultaneous diagonal flips in plane triangulations

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

doi:10.1145/1109557.1109582

Simultaneous diagonal flips in plane triangulations

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher	Association for Computing Machinery (ACM)
Pages	212-221
Number of pages	10
DOIs	https://doi.org/10.1145/1109557.1109582
Publication status	Published - 2006
Externally published	Yes

Access to Document

10.1145/1109557.1109582

Cite this

@inproceedings{86ba09e4406541a1ac6138e14818d271,

title = "Simultaneous diagonal flips in plane triangulations",

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.",

author = "Prosenjit Bose and Jurek Czyzowicz and Zhicheng Gao and Pat Morin and Wood, \{David R.\}",

year = "2006",

doi = "10.1145/1109557.1109582",

language = "English",

pages = "212--221",

booktitle = "Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery (ACM)",

address = "United States of America",

}

TY - GEN

T1 - Simultaneous diagonal flips in plane triangulations

AU - Bose, Prosenjit

AU - Czyzowicz, Jurek

AU - Gao, Zhicheng

AU - Morin, Pat

AU - Wood, David R.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

U2 - 10.1145/1109557.1109582

DO - 10.1145/1109557.1109582

M3 - Conference Paper

SP - 212

EP - 221

BT - Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery (ACM)

ER -