Schnyder Woods
In two seminal papers published around 1990 Walter Schnyder
used a specific partition of the edges of a planar triangulation
into three trees to prove two fundamental results.
Schnyder's first theorem. A graph is planar if and only if the
dimension of its incidence poset is at most 3.
Schnyder's second theorem. Every planar graph
with n vertices admits a straight line drawing on a
(n-2)x(n-2) grid.
In recent years it turned out that Schnyder tree partitions,
now called Schnyder woods, have many more uses. They appear
in the context of enumerative questions and even in algebra.
We have contributed to the theory in several papers:
Dimension of vertex-face posets and orthogonal surfaces
(Brightwell Trotter Theorem)
Lattice Structures and Drawings
Dimension of posets related to planar graphs