Laboratoire d'informatique de l'École polytechnique

Sémin'Ouvert : « Combinatorics and applications of Schnyder woods » par Éric Fusy

Speaker: Éric Fusy
Location: Bât. Turing, amphi. Germain
Date: Thu, 18 May 2017, 14:30-15:30

Schnyder woods are combinatorial structures on planar triangulations (maximal planar graphs embedded on the sphere) that can be formulated as a certain partition of the edges into 3 spanning trees. These structures have found many algorithmic applications, for instance in graph drawing, succinct encoding of meshes, efficient routing in planar networks, etc. I will present some of these applications, with an emphasis on the interplay with combinatorics.