Academic
Publications
Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to Encoding

Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to Encoding,10.1007/s00454-009-9169-z,Discrete & Computational Geometry,Luca

Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to Encoding   (Citations: 1)
BibTex | RIS | RefWorks Download
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 sur- faces 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. This is the extended and revised journal version of a conference paper with the title "Schnyder woods generalized to higher genus triangulated surfaces", which appeared in the Proceedings of the ACM Symposium on Computational Geometry 2008 (pages 311-319).
Journal: Discrete & Computational Geometry - DCG , vol. 42, no. 3, pp. 489-516, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: