2025/07/30 by Kaykobad, Tanvir
paper · doi:10.20382/jocg.v16i1a15
Any two n-vertex combinatorial triangulations are transformable to on another using a finite sequence of diagonal flips. It has been established that O(n) individual flips suffice to complete this transformation. It is known that the transformation can also be done with no more than 4 × (\frac2log(12)/(11) + \frac2log(9)/(7)) logn + 2 ≈ 85.8 logn simultaneous flips—each comprising a set of diagonal flips that yields a graph which remains both simple and planar. This bound is asymptotically tight. By processing the interior and exterior of a Hamiltonian cycle in parallel and in an interlaced fashion, we further reduce this bound down to \frac12log(6)/(5) logn ≈ 45.6 logn.