Petite École de Combinatoire (2002-2003)

Mars 2004: Stefan Felsner (Berlin), Planar graphs, Schnyder Woods and Orthogonal Surfaces

A beautiful theorem of Walter Schnyder characterizes planar graphs as the graphs of dimension at most three. The tool for proving the theorem is a special partition of the interior edges of a planar triangulation into three trees, we call such a partition a Schnyder wood.

The topics of these lectures include: