Simultaneous Diagonal Flips in Plane Triangulations

Details Simultaneous Diagonal Flips in Plane Triangulations Simultaneous Diagonal Flips in Plane Triangulations

2005-09-21

arxiv.org/abs/math/0509478v2

J. Graph Theory 54(4):307-330, 2007

Mathematics

Combinatorics

A short version of this paper will be presented at SODA 2006

Scientific paper

10.1002/jgt.20214

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

Affiliated with

Also associated with

No associations

Rating

Simultaneous Diagonal Flips in Plane Triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simultaneous Diagonal Flips in Plane Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simultaneous Diagonal Flips in Plane Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-486503