10.20381/RUOR-24732
Kaykobad, M Tanvir
Transforming Plane Triangulations by Simultaneous Diagonal Flips
Université d'Ottawa / University of Ottawa
2020
Computational geometry
Graph
Planar graph
Combinatorial triangulation
Simple planar triangulation
Diagonal flip
Simultaneous flip
Hamiltonian
Canonical triangulation
Outerplanar graph
My University
My University
2020-05-13
2020-05-13
2020-05-13
http://hdl.handle.net/10393/40499
We explore the problem of transforming plane triangulations using simultaneous diagonal flips. Wagner showed that any n-vertex plane triangulation can be transformed to any other plane triangulation on equal number of vertices using a finite sequence of diagonal flips. Later on it has been established that O(n) individual flips suffice to complete this transformation. Bose et al. showed that the transformation can also be done in 4 × ( 2 / log 54/53 + 2 / log 6/5 ) logn + 2 ≈ 327.1 log n simultaneous flips. This bound is asymptotically tight. We present two algorithms to improve the leading coefficient of this bound for transforming any plane triangulation into any other. The first of the two algorithms lowers this bound down to 4 × ( 2 / log 12/11 + 2 / log 9/7 ) logn + 2 ≈ 85.8 log n. By processing and preprocessing the interior and exterior of the triangulation’s Hamiltonian cycle parallelly in an interlaced fashion, we make further improvement of the algorithm from ≈ 327.1 log n down to 12 / log 6/5 logn + 2 ≈ 45.6 log n.