2009 Discrete Maths Seminar - 07
- Date: 04/07/2009
Lecturer(s):
Eric Fusy (UBC/LIX)
Location:
University of British Columbia
Topic:
Schnyder woods generalized to higher genus surfaces
Description:
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.
Schedule:
4:00pm-5:00pm, WMAX 216
Sponsor:
