A simple Schnyder drawing algorithm for cylindric and toroidal triangulations, with grid size \(O(n) \times O(n)\)

We consider the problem of computing a straight-line crossing-free and periodic grid drawing of cylindric and toroidal triangulations. More precisely, given a cylindric simple triangulation \(G\) with \(n\) vertices, we design an algorithm based on the Schnyder face-counting principle that computes an \(x\)-periodic drawing of \(G\) on an integer grid of size \(w \times h\), with \(w \le 2n, h \le 6n\). As a byproduct, this yields an algorithm that computes an \(xy\)-periodic drawing of a simple toroidal triangulation with \(n\) vertices on a grid of size \(w \times h\), with \(w \le 4n, h \le 10n\). A vertex-counting variant improves the grid bounds to \(w \le n, h \le 3n\) in the cylindric case and \(w \le 2n, h \le 5n\) in the toroidal case. Our algorithm is simple to describe and implement, and runs in linear time.