Résumé : We consider the problem of computing Schnyder woods for graphs embedded on the torus. We design simple linear-time algorithms based on canonical orderings that compute toroidal Schnyder woods for simple toroidal triangulations. The Schnyder woods computed by one of our algorithm are crossing and satisfy an additional structural property: at least two of the mono-chromatic components of the Schnyder wood are connected. We also exhibit experimental results empirically confirming three conjectures involving the structure of toroidal and higher genus Schnyder woods. (to be presented at SoCG'25) Joint work with Eric Fusy (Laboratoire d'Informatique Gaspard Monge), Jyh-Chwen KO and Razvan Stefan Puscasu (LIX, Ecole Polytechnique)

Dernière modification : Tuesday 11 February 2025

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr