---

Mardi 3 Juin 2008, 14h00, Salle S16 (Passage Saumon, niveau -1)

• Orateur/Speaker : Luca Castelli Aleardi, ULB
• Titre/Title : Schnyder woods for higher genus triangulated surfaces
• Résumé/Abstract
  Schnyder woods are a well known combinatorial structure for planar graphs, which yields a decomposition into 3 vertex-spanning trees. Our goal is to extend definitions and algorithms for Schnyder woods designed for planar graphs (corresponding to combinatorial surfaces with the topology of the sphere, i.e., of genus 0) to the more general case of graphs embedded on surfaces of arbitrary genus.
  
  First, we define a new traversal order of the vertices of a triangulated surface of genus g together with an orientation and coloration of the edges that extends the one proposed by Schnyder for the planar case.
  
  We are also able to provide a characterization of our edge coloring in terms of genus g maps.
  
  As a by-product we show how some recent schemes for compression and compact encoding of graphs can be extended to higher genus.
  
  (joint work with E. Fusy and T. Lewiner, to be presented at SoCG'08)