Toroidal Schnyder woods

Computation of toroidal Schnyder woods made simple: a fast and practical algorithm

(Luca Castelli Aleardi, Eric Fusy, Jyh-Chwen Ko and Puscasu Razvan-Stefan to be presented at the 41st Int. Symp. on Computational Geometry 2025)

We consider the problem of computing Schnyder woods for graphs embedded on the torus. We design and implement a simple linear-time algorithm based on canonical orderings that computes crossing toroidal Schnyder woods for simple toroidal triangulations.

We also exhibit experimental results empirically confirming two conjectures involving the structure of higher genus Schnyder woods.

License (LGPL version 3.0)

The Java implementation of our algorithm for computing toroidal Schnyder woods and related data structures is made available under the terms of the GNU Lesser General Public License (LGPL version 3.0)
This library is distributed for academic purposes in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Datasets (toroidal triangulations)

Toroidal 3D triangulations: examples of genus 1 (closed) triangle meshes in OFF format are provided here

Tiny toroidal triangulations (for exhaustive generation): the list of all genus 1 (simple and closed) triangulations generated by surftri software by Thom Sulanke is provided here

Files to download (for running tests and benchmarks: Java 1.8 or higher required)

Runnable files (the .jar files below include all required java libraries)

TestToroidalSW.jar (compiled with Java 1.8): a runnable .jar file for testing the computation of toroidal Schnyder woods (it takes as input a genus 1 mesh in OFF format)
SurfSW.jar (compiled with Java 1.8): a runnable .jar file for the exhaustive generation of toroidal Schnyder woods for graphs of tiny size (n<12). It takes as input a list of triangulations encoded in SurfTri format (see datasets above).
readme.txt: readme file illustrating how to run the .jar files

How to run the programs

Exhaustive generation of surface Schnyder woods (for tiny triangulations of genus 1 and 2)

Input format: triangulations must be provided in surftri format. Only simple triangulations without boundaries (closed manifold) are accepted.

Input arguments (at least two arguments are required to run the tests):

     Supported options are listed below
	-slow      	 run the computation in SLOW (brute-force) mode
	-check     	 check the combinatorial validity of input triangulations
	-countSW   	 generate all 3-orientations and count the number of valid Schnyder woods (g>=1)
	-findSW    	 compute and output a valid Schnyder wood (g>=1)
	-countCCSW 	 (only for g=1, SLOW mode) count the number of crossing and connected Schnyder woods [very slow for n>10]
	-findCCSW  	 (only for g=1, SLOW mode) compute and output a crossing and connected Schnyder woods [very slow for n>10]

Usage examples (running from a Terminal):

java -jar SurfSW.jar genus2_10.alpha -countSW   #(count the number of all distinct Schnyder woods for triangulations of genus 2 and size 10)

java -jar SurfSW.jar genus2_11.alpha -findSW   #(compute all distinct Schnyder woods for triangulations of genus 2 and size 11)

java -jar SurfSW.jar genus1_irreducible.txt -countCCSW -slow   #(count the number of crossing and connected Schnyder woods for all irreducible triangulations of genus 1)

java -jar SurfSW.jar genus1_irreducible.txt -findCCSW -slow   #(compute and output a crossing and connected Schnyder wood for all irreducible triangulations of genus 1)