We show that any triangulation on n vertices can be transformed into a 4-connected one using at most (3n−7)/5 edge flips. We also give an example of a triangulation that requires (3n − 10)/5 flips to be made 4-connected, showing that our bound is tight. In addition, we improve the upper bound on the number of flips required to transform any 4-connected triangulation into the canonical triangulation (the triangulation with two dominant vertices), matching the known lower bound of 2n − 15. Our results imply a new upper bound on the diameter of the flip graph of 5.2n − 32.8, improving on the previous best known bound of 6n − 30.
Combinatorial bounds on the number of flips required have also been studied and the best known upper bound is by Bose et al. REF of 5.2n − 24.4.
Making triangulations 4-connected using flips
Computational Geometry: Theory and Applications, 47(2A):187-197, 2014. Special issue for CCCG 2011
Mathematics Computer Science