Department of
Applied
Mathematics

Bounds on the diameter of the flip graph

Maria Saumell

Abstract

Given a combinatorial embedding of a triangulation, an edge flip is an operation that transforms the triangulation into a different one by replacing the diagonal of a quadrilateral formed by two adjacent triangles with the other possible diagonal. The flip graph is the graph with a vertex for each distinct triangulation and an edge between two vertices if their corresponding triangulations differ by a single flip. The flip graph is connected, and thus it makes sense to consider its diameter. In this talk we give an overview of the problem of finding upper and lower bounds on the diameter of the flip graph, and in particular we present the proof of the most recent upper bound of 5.2n - 30.8.