  Schnyder woods are a well-known combinatorial structure for plane
triangulations, which yields a decomposition into 3 spanning trees. We extend
here definitions and algorithms for Schnyder woods to closed orientable
surfaces of arbitrary genus. In particular, we describe a method to traverse a
triangulation of genus $g$ and compute a so-called $g$-Schnyder wood on the
way. As an application, we give a procedure to encode a triangulation of genus
$g$ and $n$ vertices in $4n+O(g \log(n))$ bits. This matches the worst-case
encoding rate of Edgebreaker in positive genus. All the algorithms presented
here have execution time $O((n+g)g)$, hence are linear when the genus is fixed.
