Making triangulations 4-connected using flips

Sander Verdonschot

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. Our result implies that any triangulation can be transformed into any other by at most 5.2n - 24.4 flips.