Carleton University
Technical Report TR-06-09
June 9, 2006
Flips in Planar Graphs
Prosenjit Bose & Ferran Hurtado
Abstract
We review a selection of results concerning edge flips in triangulations and planar graphs concentrating mainly on various aspects of the following problem: Given two different planar graphs of the same size, how many edge flips are necessary and sufficient to transform one graph into another. We study the problem both from a combinatorial perspective (where only a combinatorial embedding of the graph is specified) and a geometric perspective (where the graph is embedded in the plane, vertices are points and edges are straight-line segments). We highlight both the similarities and differences of the two settings, describe many extensions and generalizations, outline several applications and mention open problems.