2009 Discrete Maths Seminar - 07
Topic
Schnyder woods generalized to higher genus surfaces
Speakers
Details
Schnyder showed in 1989 that every plane triangulation has a partition
of its (inner) edges into 3 trees spanning all (inner) vertices. The
so-called Schnyder woods are a powerful combinatorial structure with
many applications: new planarity criterion, straight-line drawing,
coding, bijective counting... In this talk, we show that the definition
of Schnyder woods admits a generalization to surfaces of any genus, and
that such a Schnyder wood can be computed efficiently. As an
application we extend a simple coding procedure to higher genus.
This is joint work with Luca Castelli Aleardi and Thomas Lewiner.
