A simple Schnyder drawing algorithm for cylindric and toroidal triangulations, with grid size O(n) × 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 × h, with w ≤ 2n, h ≤ 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×h, with w ≤ 4n, h ≤ 10n. A vertex-counting variant improves the grid bounds to w ≤ n, h ≤ 3n in the cylindric case and w ≤ 2n, h ≤ 5n in the toroidal case. Our algorithm is simple to describe and implement, and runs in linear time.