Schnyder woods for higher genus triangulated surfaces, with applications to encoding

الأصل · EN

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 (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.