2016 Journal of Complexity best paper award 2017-05-04
The laboratory LIX
The abbreviation LIX stands for Laboratoire d'Informatique de l'Ecole polytechnique (Laboratory of Informatics of the École polytechnique), where the letter X represents the Polytechnique per French tradition. LIX is a mixed research unit (UMR 7161) consisting of two tutelles: the École polytechnique and the National Center for Scientific Research (CNRS). LIX falls under the jurisdiction of the INS2I division (which stands for the National Institute of Sciences of Information and their Interactions) of CNRS.
Sémin'Ouvert : « Combinatorics and applications of Schnyder woods » par Éric Fusy
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.