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

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

2009-04-17

arxiv.org/abs/0904.2776v1

Mathematics

Combinatorics

27 pages, to appear in a special issue of Discrete and Computational Geometry

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Schnyder woods for higher genus triangulated surfaces, with applications to encoding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Schnyder woods for higher genus triangulated surfaces, with applications to encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Schnyder woods for higher genus triangulated surfaces, with applications to encoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-141982