Schnyder woods for higher genus triangulated surfaces

We study a well-known characterization of planar graphs, also called Schnyder wood or Schnyder labeling, which yields a decomposition into vertex spanning trees. The goal is to extend previous algorithms and characterizations designed for planar graphs (corresponding to combinatorial surfaces with the topology of the sphere, i.e., of genus 0) to the more general case of graphs embedded on surfaces of arbitrary genus. First, we define a new traversal order of the vertices of a triangulated surface of genus g together with an orientation and coloration of the edges that extends the one proposed by Schnyder for the planar case. As a by-product we show how some recent schemes for compression and compact encoding of graphs can be extended to the higher genus case. All the algorithms presented here have linear time complexity.