Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Marked Items 
Alerts
Order History
Saved Items
All
Favorites
    
Book Chapter Printable view
Optimal Coding and Sampling of Triangulations

Optimal Coding and Sampling of Triangulations

Book SeriesLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISSN0302-9743 (Print) 1611-3349 (Online)
VolumeVolume 2719/2003
BookAutomata, Languages and Programming
DOI10.1007/3-540-45061-0
Copyright2003
ISBN978-3-540-40493-4
DOI10.1007/3-540-45061-0_83
Page191
Subject CollectionComputer Science
SpringerLink DateWednesday, January 01, 2003
Add to marked items

Optimal Coding and Sampling of Triangulations

Dominique Poulalhon5 Contact Information and Gilles Schaeffer5 Contact Information

(5)  École polytechnique, LIX — CNRS, 91128 Palaiseau Cedex, France
Abstract
We present a bijection between the set of plane triangulations (aka. maximal planar graphs) and a simply defined subset of plane trees with two leaves per inner node. The construction takes advantage of the minimal realizer (or Schnyder tree decomposition) of a plane triangulation.
This yields a simple interpretation of the formula for the number of plane triangulations with n vertices. Moreover the construction is simple enough to induce a linear random sampling algorithm, and an explicit information theory optimal encoding.

Contact Information Dominique Poulalhon
Email: Dominique.Poulalhon@lix.polytechnique.fr
URL: http://lix.polytechnique.fr/Labo/

Contact Information Gilles Schaeffer
Email: Gilles.Schaeffer@lix.polytechnique.fr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.
more options
Find


Export this chapter
Export this chapter as RIS | Text
 
Referenced by
1 newer article

  1. Dunfield, Nathan M (2006) A random tunnel number one 3–manifold does not fiber over the circle. Geometry & Topology 10
    [CrossRef]
Frequently asked questions | General information on journals and books | Send us your feedback | Impressum | Contact
© Springer. Part of Springer Science+Business Media
Privacy, Disclaimer, Terms and Conditions, © Copyright Information
Remote Address: 38.107.191.105 • Server: mpweb07
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)