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

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-00712046
Contributor : Luca Castelli Aleardi <>
Submitted on : Tuesday, June 26, 2012 - 11:57:12 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on: Thursday, September 27, 2012 - 2:40:08 AM

File

SchnyderWoods_DCG09_Hal.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Luca Castelli Aleardi, Eric Fusy, Thomas Lewiner. Schnyder woods for higher genus triangulated surfaces, with applications to encoding. Discrete and Computational Geometry, Springer Verlag, 2009, 42 (3), pp.489-516. ⟨10.1007/s00454-009-9169-z⟩. ⟨hal-00712046⟩

Share

Metrics

Record views

290

Files downloads

232