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: 

pims