Flippable Edges in Triangulations on Surfaces

Abstract

Concerning diagonal flips on triangulations, Gao et al. showed that any triangulation G on the sphere with n ≥ 5 vertices has at least n − 2 flippable edges. Furthermore, if G has minimum degree at least 4 and n ≥ 9, then G has at least 2n + 3 flippable edges. In this paper, we give a simpler proof of their results, and extend them to the case of the projective plane, the torus and the Klein bottle. Finally, we give an estimation for the number of flippable edges of a triangulation on general surfaces, using the notion of irreducible triangulations.

Keywords

• triangulation
• diagonal flip
• surface
• 05c10