article

Optimal Coding and Sampling of Triangulations

Authors:

Dominique Poulalhon,

Gilles SchaefferAuthors Info & Claims

Algorithmica, Volume 46, Issue 3-4

Pages 505 - 527

Published: 01 November 2006 Publication History

Abstract

We present a bijection between the set of plane triangulations (aka maximal planar graphs) and a simple subset of the set of plane trees with two leaves adjacent to each node. The construction takes advantage of Schnyder tree decompositions of plane triangulations. This bijection yields an 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. Finally, we extend our bijection approach to triangulations of a polygon with k sides with m inner vertices, and develop in passing new results about Schnyder tree decompositions for these objects.

References

[1]

M.E. Agishtein and A.A. Migdal. Geometry of a two-dimensional quantum gravity: numerical study. Nuclear Phys. B, 350:690-728, 1991.

[2]

L. Alonso, J.-L. Remy, and R. Schott. A linear-time algorithm for the generation of trees. Algorithmica, 17(2):162-183, 1997.

[3]

J. Ambjørn, P Bialas, Z. Burda, J. Jurkiewicz, and B. Petersson. Effective sampling of random surfaces by baby universe surgery. Phys. Lett. B, 325:337-346, 1994.

[4]

J. Ambjørn, B. Durhuus, and T. Jonsson. Quantum Geometry. Cambridge Monographs on Mathematical Physics. Cambridge University Press, Cambridge, 1997.

[5]

C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. Planar maps and Airy phenomena. In Proc. ICALP, pages 388-402, 2000.

[6]

N. Bonichon. A bijection between realizers of maximal plane graphs and pairs of non-crossing dyck paths. In Proc. FPSAC, 2002.

[7]

N. Bonichon, C. Gavoille, and N. Hanusse. An information-theoretic upper bound of planar graphs using triangulation. In Proc. STACS, 2003.

[8]

N. Bonichon, B. Le Saëc, and M. Mosbah. Wagner's theorem on realizers. In Proc. ICALP, pages 1043-1053, 2002.

[9]

M. Bousquet-Melou and G. Schaeffer. The degree distribution in bipartite planar maps: applications to the Ising model. 2002, arXiv:math.CO/0211070.

[10]

E. Brehm. 3-Orientations and Schnyder 3-tree-decompositions. Master's thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000.

[11]

W. Brown. Enumeration of triangulations of the disk. Proc. London Math. Soc. (3), 14:746-768, 1964.

[12]

L. Castelli Aleardi, O. Devillers, and G. Schaeffer. Succinct representation of triangulations with a boundary. In Proc. WADS, pages 139-195. LNCS 3608, Springer, Berlin, 2005.

Digital Library

[13]

R. C.-N. Chuang, A. Garg, X. He, M.-Y. Kao, and H.-I Lu. Compact encodings of planar graphs via canonical orderings. In Proc. ICALP, pages 118-129, 1998.

[14]

H. de Fraysseix and P. Ossona de Mendez. Regular orientations, arboricity and augmentation. In Proc. Graph Drawing, pages 111-118. LNCS 894, Springer, Berlin, 1995.

[15]

P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer. Random sampling from boltzmann principles. In Proc. ICALP, pages 501-513, 2002.

[16]

A. Dvoretzky and Th. Motzkin. The asymptotic density of certain sets of real numbers. Duke Math. J., 14:315-321, 1947.

[17]

S. Felsner. Convex drawings of planar graphs and the order dimension of 3-polytopes. Order, 18:19-37, 2001.

[18]

S. Felsner. Lattice structures from planar graphs. Electron. J. Combin., 11:#15, 24 pp., 2004.

[19]

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.

Digital Library

[20]

E. Fusy, D. Poulalhon, and G. Schaeffer. Dissections and trees, with applications to optimal mesh encoding and to random sampling. In Proc. SODA, pages 690-699, 2005.

[21]

P.-M. Gandoin and O. Devillers. Progressive lossless compression of arbitrary simplicial complexes. ACM Trans. Graphics, 21(3):372-379, 2002.

Digital Library

[22]

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.

Digital Library

[23]

O. Gimenez and M. Noy. Asymptotic enumeration and limit law of labelled planar graphs. Preprint available on arXiv.org, 2005.

[24]

X. He, M.-Y. Kao, and H.-I. Lu. Linear-time succinct encodings of planar graphs via canonical orderings. SIAM J. Discrete Math., 12(3):317-325, 1999.

Digital Library

[25]

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.

Digital Library

[26]

G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996. (also Proc. FOCS 92).

[27]

D. King and J. Rossignac. Guaranteed 3.67v bit encoding of planar triangle graphs. In Proc. CCCG, #39, 1999.

[28]

H.-I. Lu. Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. In Proc. SODA, pages 223-224, 2002.

Digital Library

[29]

J. I. Munro and V. Raman. Succint representation of balanced parantheses and static trees. SIAM J. Comput., 31:762-776, 2001.

Digital Library

[30]

D. Osthus, H.J. Prömel, and A. Taraz. On random planar graphs, the number of planar graphs and their triangulations. J. Combin. Theory, Ser. B, 88(1):119-134, May 2003.

Digital Library

[31]

D. Poulalhon and G. Schaeffer. A bijection for triangulations of a polygon with interior points and multiple edges. Theoret. Comput. Sci., 307(2):385-401, 2003.

Digital Library

[32]

L. B. Richmond and N. C. Wormald. Almost all maps are asymmetric. J. Combin. Theory Ser. B, 63(1):1-7, 1995.

Digital Library

[33]

J. Rossignac. Edgebreaker: connectivity compression for triangle meshes. IEEE Trans. Visual. Comput. Graphics, 5(1):47-61, 1999.

Digital Library

[34]

G. Schaeffer. Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees. Electron. J. Combin., 4(1):# 20, 14 pp., 1997.

[35]

G. Schaeffer. Conjugaison d'arbres et cartes combinatoires aléatoires. Ph.D. thesis, Université Bordeaux I, 1998.

[36]

G. Schaeffer. Random sampling of large planar maps and convex polyhedra. In Proc. STOC, pages 760-769, 1999.

Digital Library

[37]

W. Schnyder. Embedding planar graphs on the grid. In Proc. SODA, pages 138-148, 1990.

[38]

C. Touma and C. Gotsman. Triangle mesh compression. In Proc. Graphics Interface, Vancouver, pages 26-34, 1998.

[39]

W. T. Tutte. A census of planar triangulations. Canad. J. Math., 14:21-38, 1962.

[40]

D. B. Wilson. Annotated bibliography of perfectly random sampling with markov chains. http://dimacs.rutgers.edu/~dbwilson/exact.

Cited By

Castelli Aleardi L(2019)Balanced Schnyder Woods for Planar Triangulations: An Experimental Study with Applications to Graph Drawing and Graph SeparatorsGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_9(114-121)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_9
Bernardi OFusy r(2018)Bijections for planar maps with boundariesJournal of Combinatorial Theory Series A10.1016/j.jcta.2018.03.001158:C(176-227)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1016/j.jcta.2018.03.001
Fang WPréville-Ratelle L(2017)The enumeration of generalized Tamari intervalsEuropean Journal of Combinatorics10.1016/j.ejc.2016.10.00361:C(69-84)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.ejc.2016.10.003
Show More Cited By

Index Terms

Optimal Coding and Sampling of Triangulations

Recommendations

Optimal two-dimensional triangulations
Optimal coding and sampling of triangulations
ICALP'03: Proceedings of the 30th international conference on Automata, languages and programming

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 ...
Acyclically 4-colorable triangulations

An acyclic k-coloring of a graph is a proper vertex k-coloring such that every bichromatic subgraph, induced by this coloring, contains no cycles. A graph is acyclically k-colorable if it has an acyclic k-coloring. In this paper, we prove that every ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 46, Issue 3-4

November 2006

309 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 2006 Springer.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Castelli Aleardi L(2019)Balanced Schnyder Woods for Planar Triangulations: An Experimental Study with Applications to Graph Drawing and Graph SeparatorsGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_9(114-121)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_9
Bernardi OFusy r(2018)Bijections for planar maps with boundariesJournal of Combinatorial Theory Series A10.1016/j.jcta.2018.03.001158:C(176-227)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1016/j.jcta.2018.03.001
Fang WPréville-Ratelle L(2017)The enumeration of generalized Tamari intervalsEuropean Journal of Combinatorics10.1016/j.ejc.2016.10.00361:C(69-84)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.ejc.2016.10.003
Despré VGonçalves DLévêque B(2017)Encoding Toroidal TriangulationsDiscrete & Computational Geometry10.1007/s00454-016-9832-057:3(507-544)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00454-016-9832-0
Duchi EPoulalhon DSchaeffer GChekuri C(2014)Uniform random sampling of simple branched coverings of the sphere by itselfProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634095(294-304)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634095
Gonçalves DLévêque B(2014)Toroidal MapsDiscrete & Computational Geometry10.1007/s00454-013-9552-751:1(67-131)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1007/s00454-013-9552-7
Castelli Aleardi LDevillers O(2011)Explicit array-based compact data structures for triangulationsProceedings of the 22nd international conference on Algorithms and Computation10.1007/978-3-642-25591-5_33(312-322)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25591-5_33
Fusy í(2010)New bijective links on planar maps via orientationsEuropean Journal of Combinatorics10.1016/j.ejc.2009.02.00831:1(145-160)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1016/j.ejc.2009.02.008
Aleardi LFusy ÉLewiner T(2009)Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to EncodingDiscrete & Computational Geometry10.5555/3116272.311651542:3(489-516)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.5555/3116272.3116515
Valette SChaine RProst RPolthier KAlexa MKazhdan M(2009)Progressive lossless mesh compression via incremental parametric refinementProceedings of the Symposium on Geometry Processing10.5555/1735603.1735610(1301-1310)Online publication date: 15-Jul-2009
https://dl.acm.org/doi/10.5555/1735603.1735610
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents