Flips in planar graphs
We review results concerning edge flips in 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 overview both the combinatorial perspective (where only a combinatorial embedding of the graph is specified) and the geometric perspective (where the graph is embedded in the plane, vertices are points and edges are straight-line segments). We highlight the similarities and differences of the two settings, describe many extensions and generalizations, highlight algorithmic issues, outline several applications and mention open problems.
|Keywords||Algorithms, Computational geometry, Local transformations, Planar graphs, Theory|
Bose, P, & Hurtado, F. (Ferran). (2009). Flips in planar graphs. Computational Geometry, 42(1), 60–80. doi:10.1016/j.comgeo.2008.04.001