We show that any triangulation on n vertices can be transformed into a 4-connected one using at most ⌊(3n - 6)/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. Our re- sult implies a new upper bound on the diameter of the flip graph of 5.2n - 24.4, improving on the bound of 6n - 30 by Mori et al. [4].

Additional Metadata
Conference 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Citation
Bose, P, Jansens, D. (Dana), Van Renssen, A. (André), Saumell, M. (Maria), & Verdonschot, S. (Sander). (2011). Making triangulations 4-connected using flips. Presented at the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011.