Transforming Plane Triangulations by Simultaneous Diagonal Flips

Abstract

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.