Simultaneous Diagonal Flips in Plane Triangulations

Simple item page
dc.creatorBose, Prosenjit
dc.creatorCzyzowicz, Jurek
dc.creatorGao, Zhicheng
dc.creatorMorin, Pat
dc.creatorWood, David R.
dc.date2005-09-21
dc.date2006-04-26
dc.date.accessioned2026-07-07T10:01:29Z
dc.date.available2026-07-07T10:01:29Z
dc.descriptionSimultaneous diagonal flips in plane triangulations are investigated. It is proved that every $n$-vertex triangulation with at least six vertices has a simultaneous flip into a 4-connected triangulation, and that it can be computed in 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 $O(\log n)$ simultaneous flips to transform one into the other. The total number of edges flipped in this sequence is 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/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.
dc.descriptionA short version of this paper will be presented at SODA 2006
dc.identifierhttps://arxiv.org/abs/math/0509478
dc.identifierhttp://arxiv.org/abs/math/0509478
dc.identifierJ. Graph Theory 54(4):307-330, 2007
dc.identifierdoi:10.1002/jgt.20214
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/168644
dc.subjectCombinatorics
dc.subjectComputational Geometry
dc.subject05C10
dc.titleSimultaneous Diagonal Flips in Plane Triangulations
dc.typetext

Files

Collections

arXiv