julianschick/schnyder-woods

Data structures for representing embedded graphs and Schnyder woods. Some algorithms working on these structures (focused on the operations 'split' and 'merge').

The Flip Graph of Split and Merge on Schnyder Woods

A 'Schnyder Wood' is a special orientation and colouring of the edges of a 3-vertex-connected planar graph that is embedded into the plane. The figure shows a Schnyder wood on 13 vertices.

The operations 'split' and 'merge' locally alters a Schnyder wood as depicted in the image below.

Split and merge are mutually inverse and can, thus, be interpreted as 'flip' and 'flop' giving rise to a classical flip graph. Below the flip graph of split and merge for n equals five (every Schnyder wood in this flip graph has five vertices) is shown.

The software package in this repository can generate these flip graphs, find paths within it and much more.