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.