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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M.E. Agishtein and A.A. Migdal. Geometry of a two-dimensional quantum gravity: numerical study. Nucl. Phys. B, 350:690–728, 1991.
L. Alonso, J.-L. Remy, and R. Schott. A linear-time algorithm for the generation of trees. Algorithmica, pages 162–183, 1997.
J. Ambjørn, P Białas, Z. Burda, J. Jurkiewicz, and B. Petersson. Effective sampling of random surfaces by baby universe surgery. Phys. Lett. B, 325:337–346, 1994.
J. Ambjørn, B. Durhuus, and T. Jonsson. Quantum geometry. Cambridge Monographs on Mathematical Physics. Cambridge University Press, Cambridge, 1997.
C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. Planar maps and Airy phenomena. In ICALP, pages 388–402, 2000.
N. Bonichon. A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths. In FPSAC, 2002.
N. Bonichon, C. Gavoille, and N. Hanusse. An information-theoretic upper bound of planar graphs using triangulations. In STACS, 2003.
N. Bonichon, B. Le Saëc, and M. Mosbah. Wagner’s theorem on realizers. In ICALP, pages 1043–1053, 2002.
M. Bousquet-Melou and G. Schaeffer. The degree distribution in bipartite planar maps: applications to the Ising model. 2002, arXiv:math.CO/0211070.
E. Brehm. 3-orientations and Schnyder 3-tree-decompositions. Master’s thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000.
R. C.-N. Chuang, A. Garg, X. He, M.-Y. Kao, and H.-I Lu. Compact encodings of planar graphs via canonical orderings. In ICALP, pages 118–129, 1998.
H. de Fraysseix and P. Ossona de Mendez. Regular orientations, arboricity and augmentation. In Graph Drawing, 1995.
P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer. Random sampling from Boltzmann principles. In ICALP, pages 501–513, 2002.
S. Felsner. Convex drawings of planar graphs and the order dimension of 3-polytopes. Order, 18:19–37, 2001.
P. Flajolet, P. Zimmermann, and B. Van Cutsem. A calculus for random generation of labelled combinatorial structures. Theoret. Comput. Sci., 132(2):1–35, 1994.
P.-M. Gandoin and O. Devillers. Progressive lossless compression of arbitrary simplicial complexes. ACM Transactions on Graphics, 21(3):372–379, 2002.
Z. Gao and J. Wang. Enumeration of rooted planar triangulations with respect to diagonal flips. J. Combin. Theory Ser. A, 88(2):276–296, 1999.
X. He, M.-Y. Kao, and H.-I Lu. Linear-time succinct encodings of planar graphs via canonical orderings. SIAM J. on Discrete Mathematics, 12(3):317–325, 1999.
X. He, M.-Y. Kao, and H.-I Lu. A fast general methodology for information-theoretically optimal encodings of graphs. SIAM J. Comput, 30(3):838–846, 2000.
G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4–32, 1996. (also FOCS’92).
D. King and J Rossignac. Guaranteed 3.67v bit encoding of planar triangle graphs. In CCCG, 1999.
H.-I Lu. Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. In SODA, pages 223–224, 2002.
D. Osthus, H.J. Prömel, and A. Taraz. On random planar graphs, the number of planar graphs and their triangulations. J. Comb. Theory, Ser. B, 2003. to appear.
D. Poulalhon and G. Schaeffer. A bijection for triangulations of a polygon with interior points and multiple edges. Theoret. Comput. Sci., 2003. to appear.
L. B. Richmond and N. C. Wormald. Almost all maps are asymmetric. J. Combin. Theory Ser. B, 63(1):1–7, 1995.
J. Rossignac. Edgebreaker: Connectivity compression for triangle meshes. IEEE Transactions on Visualization and Computer Graphics, 5(1):47–61, 1999.
G. Schaeffer. Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees. Electron. J. Combin., 4(1):# 20, 14 pp., 1997.
G. Schaeffer. Conjugaison d’arbres et cartes combinatoires aléatoires. PhD thesis, Université Bordeaux I, 1998.
G. Schaeffer. Random sampling of large planar maps and convex polyhedra. In STOC, pages 760–769, 1999.
W. Schnyder. Embedding planar graphs on the grid. In SODA, pages 138–148, 1990.
W. T. Tutte. A census of planar triangulations. Canad. J. Math., 14:21–38, 1962.
D. B. Wilson. Annotated bibliography of perfectly random sampling with Markov chains. http://dimacs.rutgers.edu/~dbwilson/exact.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Poulalhon, D., Schaeffer, G. (2003). Optimal Coding and Sampling of Triangulations. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds) Automata, Languages and Programming. ICALP 2003. Lecture Notes in Computer Science, vol 2719. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45061-0_83
Download citation
DOI: https://doi.org/10.1007/3-540-45061-0_83
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40493-4
Online ISBN: 978-3-540-45061-0
eBook Packages: Springer Book Archive