Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Computational Geometry
Spanning Tree
Subscribe
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/s004540099169z,Discrete & Computational Geometry,Luca
Edit
Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to Encoding
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Luca Castelli Aleardi
,
Éric Fusy
,
Thomas Lewiner
Schnyder woods are a wellknown 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 socalled gSchnyder 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 worstcase 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 311319).
Journal:
Discrete & Computational Geometry  DCG
, vol. 42, no. 3, pp. 489516, 2009
DOI:
10.1007/s004540099169z
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
(
arxiv.org
)
(
algo.inria.fr
)
More »
References
(44)
Succinct Representation of Labeled Graphs
(
Citations: 9
)
Jérémy Barbay
,
Luca Castelli Aleardi
,
Meng He
,
J. Ian Munro
Conference:
International Symposium on Algorithms and Computation  ISAAC
, pp. 316328, 2007
Intervals in Catalan lattices and realizers of triangulations
(
Citations: 10
)
Olivier Bernardi
,
Nicolas Bonichon
Journal:
Journal of Combinatorial Theory  JCT
, vol. 116, no. 1, pp. 5575, 2009
An InformationTheoretic Upper Bound of Planar Graphs Using Triangulation
(
Citations: 28
)
Nicolas Bonichon
,
Cyril Gavoille
,
Nicolas Hanusse
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, pp. 499510, 2003
Planar Graphs, via WellOrderly Maps and Trees
(
Citations: 15
)
Nicolas Bonichon
,
Cyril Gavoille
,
Nicolas Hanusse
,
Dominique Poulalhon
,
Gilles Schaeffer
Journal:
Graphs and Combinatorics
, vol. 22, no. 2, pp. 185202, 2006
Edge Partition of Toroidal Graphs into Forests in Linear Time
(
Citations: 4
)
Nicolas Bonichon
,
Cyril Gavoille
,
Arnaud Labourel
Journal:
Electronic Notes in Discrete Mathematics
, vol. 22, pp. 421425, 2005
Sort by:
Citations
(1)
A Note on Schnyder’s Theorem
Fidel BarreraCruz
,
Penny Haxell
Journal:
A Journal on The Theory of Ordered Sets and Its Applications  Order
, vol. 28, no. 2, pp. 221226, 2011