2026-07-23T22:18:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23182 2025-10-02T12:42:13Z ddc:004 open_access

Computation of Toroidal Schnyder Woods Made Simple and Fast: From Theory to Practice Castelli Aleardi, Luca Fusy, Eric Ko, Jyh-Chwen Puscasu, Razvan-Stefan Schnyder woods toroidal triangulations canonical ordering 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luca Castelli Aleardi and Eric Fusy and Jyh-Chwen Ko and Razvan-Stefan Puscasu 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.30 urn:nbn:de:0030-drops-231825 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.30 eng https://creativecommons.org/licenses/by/4.0/legalcode