research-article

Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling

Authors:

Gilles Schaeffer,

Dominique PoulalhonAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 4, Issue 2

Article No.: 19, Pages 1 - 48

https://doi.org/10.1145/1361192.1361196

Published: 29 May 2008 Publication History

Abstract

We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees with interesting consequences for enumeration, mesh compression, and graph sampling. Our bijection yields an efficient uniform random sampler for 3-connected planar graphs, which turns out to be determinant for the quadratic complexity of the current best-known uniform random sampler for labelled planar graphs. It also provides an encoding for the set P(n) of n-edge 3-connected planar graphs that matches the entropy bound 1/n log₂ |P(n)| = 2 + o(1) bits per edge (bpe). This solves a theoretical problem recently raised in mesh compression as these graphs abstract the combinatorial part of meshes with spherical topology. We also achieve the optimal parametric rate 1/n log₂ |P(n, i, j)| bpe for graphs of P(n) with i vertices and j faces, matching in particular the optimal rate for triangulations. Our encoding relies on a linear time algorithm to compute an orientation associated with the minimal Schnyder wood of a 3-connected planar map. This algorithm is of independent interest, and it is, for instance, a key ingredient in a recent straight line drawing algorithm for 3-connected planar graphs.

References

[1]

Alliez, P. and Gotsman, C. 2003. Recent advances in compression of 3D meshes. In Proceedings of the Symposium on Multiresolution in Geometric Modeling. http://www.inria.fr/rrrt/rr-4966.

[2]

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

[3]

di Battista, G., Tamassia, R., and Vismara, L. 1999. Output-sensitive reporting of disjoint paths. Algorithmica 23, 3, 302--340.

[4]

Bender, E. A. 1987. The number of three-dimensional convex polyhedra. Amer. Math. Month. 94, 1, 7--21.

Digital Library

[5]

Bodirsky, M., Gröpl, C., and Kang, M. 2003. Generating labeled planar graphs uniformly at random. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP'03). Eindhoven, The Netherlands. 1095--1107.

Digital Library

[6]

Bonichon, N., Felsner, S., and Mosbah, M. 2007. Convex drawings of 3-connected planar graphs. Algorithmica 47, 4, 399--420.

Digital Library

[7]

Bonichon, N., Gavoille, C., and Hanusse, N. 2003. An information-theoretic upper bound of planar graphs using triangulations. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS'03), 499--510.

Digital Library

[8]

Bouttier, J., di Francesco, P., and Guitter, E. 2002. Census of planar maps: from the one-matrix solution to a combinatorial proof. Nucl. Phys. B 645, 477--499.

[9]

Brehm, E. 2000. 3-orientations and Schnyder 3-tree-decompositions. M.S. thesis, Freie Universität Berlin, Germany. http://www.tu-berlin.de/ ~felsner/Diplomarbeiten/brehm.ps.gz.

[10]

Brown, W. 1964. Enumeration of triangulations of the disk. In Proceedings of the London Mathematical Society. 746--768.

[11]

Castelli-Aleardi, L. and Devillers, O. 2004. Canonical triangulation of a graph, with a coding application. http://www.inria.fr/rrrt/rr-5231.html.

[12]

Castelli-Aleardi, L., Devillers, O., and Schaeffer, G. 2006. Optimal succinct representations of planar maps. In Proceedings of ACM Symposium on Computational Geometry (SoCG'06), Sedona, AZ. ACM Press, 309--318.

Digital Library

[13]

Chuang, R. C.-N., Garg, A., He, X., Kao, M.-Y., and Lu, H.-I. 1998. Compact encodings of planar graphs via canonical orderings. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP'98), Aalborg, Denmark.

Digital Library

[14]

Denise, A., Vasconcellos, M., and Welsh, D. J. A. 1996. The random planar graph. Congr. Numer. 113, 61--79.

[15]

Duchon, P., Flajolet, P., Louchard, G., and Schaeffer, G. 2004. Boltzmann samplers for the random generation of combinatorial structures. Combinatorics Probab. Comput. (Special Issue on Analysis of Algorithms.) 13, 4--5, 577--625.

Digital Library

[16]

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

[17]

Felsner, S. 2004. Lattice structures for planar graphs. Electron. J. Comb. 11, 1.

[18]

Flajolet, P., Zimmermann, P., and Van Cutsem, B. 1994. A calculus for random generation of combinatorial structures. Theoret. Comput. Sci. 132, 2, 1--35.

Digital Library

[19]

de Fraysseix, H., Ossona de Mendez, P., and Rosenstiehl, P. Pigale, Automatic Graph Drawing. http://sourceforge.org/pigale/.

[20]

Fusy, É. 2005. Quadratic exact size and linear approximate size random generation of planar graphs. Discr. Math. Theor. Comput. Sci. AD, 125--138.

[21]

Gessel, I. 1992. Super ballot numbers. J. Symb. Comput. 14, 2/3, 179--194.

Digital Library

[22]

Gotsman, C. 2003. On the optimality of valence-based connectivity coding. Comput. Graph. Foru., 99--102.

[23]

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

Digital Library

[24]

He, X., Kao, M.-Y., and Lu, H.-I. 2000. A fast general methodology for information-theoretically optimal encodings of graphs. SIAM J. Comput 30, 3, 838--846.

Digital Library

[25]

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

[26]

Khodakovsky, A., Alliez, P., Desbrun, M., and Schröder, P. 2002. Near-optimal connectivity encoding of polygon meshes. Graph. Model 64, 3--4.

Digital Library

[27]

Khuller, S., Naor, J., and Klein, P. N. 1993. The lattice structure of flow in planar graphs. SIAM J. Discr. Math. 6, 3 477--490.

Digital Library

[28]

Lu, H.-I. 2002. Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. In Proceedings of Symposium on Discrete Algorithms (SODA'02), San Francisco, CA. ACM Press, 223--224.

Digital Library

[29]

McDiarmid, C., Steger, A., and Welsh, D. 2005. Random planar graphs. J. Combin. Theory, Series B 93, 187--205.

Digital Library

[30]

Mullin, R. and Schellenberg, P. 1968. The enumeration of c-nets via quadrangulations. J. Combin. Theory 4, 259--276.

[31]

Munro, J. I. and Raman, V. 1997. Succinct representation of balanced parentheses, static trees and planar graphs. In Proceedings of Annual Symposium on Foundations of Computer Science (FOCS'97), Miami, FL. ACM Press, 118--126.

Digital Library

[32]

Nijenhuis, A. and Wilf, H. S. 1978. Combinatorial Algorithms, 2nd Ed. Academic Press.

[33]

Ossona de Mendez, P. 1994. Orientations bipolaires. Ph.D. thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, France.

[34]

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

Digital Library

[35]

Poulalhon, D. and Schaeffer, G. 2006. Optimal coding and sampling of triangulations. Algorithmica 46(3-4), 505--527.

Digital Library

[36]

Rossignac, J. 1999. Edgebreaker: Connectivity compression for triangle meshes. IEEE Trans. Visualiz. Comput. Graph. 5, 1, 47--61.

Digital Library

[37]

Schaeffer, G. 1997. Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees. Electron. J. Combin. 4, 1, &num; 20, 14 pp.

[38]

Schaeffer, G. 1999. Random sampling of large planar maps and convex polyhedra. In Proceedings of ACM Symposium on the Theory of Computing (STOC'99), Atlanta, CA. ACM Press, 760--769.

Digital Library

[39]

Schnyder, W. 1990. Embedding planar graphs on the grid. In Proceedings of Symposium on Discrete Algorithms (SODA'90), San Francisco, CA. ACM Press, 138--148.

Digital Library

[40]

Touma, C. and Gotsman, C. 1998. Triangle mesh compression. In Graphic Interface Conference 26--34.

[41]

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

[42]

Tutte, W. T. 1963. A census of planar maps. Canad. J. Math. 15, 249--271.

[43]

Whitney, H. 1933. 2-isomorphic graphs. Amer. J. Math. 54, 245--254.

[44]

Wilson, D. B. 1997. Determinant algorithms for random planar structures. In Proceedings of Symposium on Discrete Algorithms (SODA'97), New Orleans, LA. ACM Press, 258--267.

Digital Library

[45]

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

Cited By

Fuentes-Sepúlveda JSeco DViaña R(2021)Succinct Encoding of Binary Strings Representing TriangulationsAlgorithmica10.1007/s00453-021-00861-483:11(3432-3468)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1007/s00453-021-00861-4
Fusy ÉLévêque B(2020)Orientations and bijections for toroidal maps with prescribed face-degrees and essential girthJournal of Combinatorial Theory, Series A10.1016/j.jcta.2020.105270175(105270)Online publication date: Oct-2020
https://doi.org/10.1016/j.jcta.2020.105270
Ferres LFuentes-Sepúlveda JGagie THe MNavarro G(2020)Fast and compact planar embeddingsComputational Geometry10.1016/j.comgeo.2020.10163089(101630)Online publication date: Aug-2020
https://doi.org/10.1016/j.comgeo.2020.101630
Show More Cited By

Index Terms

Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics

Recommendations

Dissections and trees, with applications to optimal mesh encoding and to random sampling
SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees. This correspondence has interesting consequences for enumeration, mesh compression and random graph sampling.It yields a succinct representation for ...
Random generation and enumeration of bipartite permutation graphs

Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation ...
Random Generation and Enumeration of Bipartite Permutation Graphs
ISAAC '09: Proceedings of the 20th International Symposium on Algorithms and Computation

Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 4, Issue 2

May 2008

204 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1361192

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 May 2008

Accepted: 01 June 2006

Revised: 01 June 2006

Received: 01 April 2005

Published in TALG Volume 4, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
379
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fuentes-Sepúlveda JSeco DViaña R(2021)Succinct Encoding of Binary Strings Representing TriangulationsAlgorithmica10.1007/s00453-021-00861-483:11(3432-3468)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1007/s00453-021-00861-4
Fusy ÉLévêque B(2020)Orientations and bijections for toroidal maps with prescribed face-degrees and essential girthJournal of Combinatorial Theory, Series A10.1016/j.jcta.2020.105270175(105270)Online publication date: Oct-2020
https://doi.org/10.1016/j.jcta.2020.105270
Ferres LFuentes-Sepúlveda JGagie THe MNavarro G(2020)Fast and compact planar embeddingsComputational Geometry10.1016/j.comgeo.2020.10163089(101630)Online publication date: Aug-2020
https://doi.org/10.1016/j.comgeo.2020.101630
Aleardi LFusy ÉLewiner T(2019)Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to EncodingDiscrete & Computational Geometry10.5555/3116272.311651542:3(489-516)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3116272.3116515
Felsner SFusy íNoy MOrden D(2019)Bijections for Baxter families and related objectsJournal of Combinatorial Theory Series A10.1016/j.jcta.2010.03.017118:3(993-1020)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.jcta.2010.03.017
Bernardi OBousquet-Mélou M(2018)Counting colored planar mapsJournal of Combinatorial Theory Series B10.1016/j.jctb.2011.02.003101:5(315-377)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.jctb.2011.02.003
Bernardi OFusy É(2018)Schnyder Decompositions for Regular Plane Graphs and Application to DrawingAlgorithmica10.1007/s00453-011-9514-562:3-4(1159-1197)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1007/s00453-011-9514-5
Ferres LFuentes JGagie THe MNavarro G(2017)Fast and Compact Planar EmbeddingsAlgorithms and Data Structures10.1007/978-3-319-62127-2_33(385-396)Online publication date: 5-Jul-2017
https://doi.org/10.1007/978-3-319-62127-2_33
Addario-Berry LLeavitt N(2016)Random infinite squarings of rectanglesAnnales de l'Institut Henri Poincaré, Probabilités et Statistiques10.1214/14-AIHP66152:2Online publication date: 1-May-2016
https://doi.org/10.1214/14-AIHP661
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
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents