Optimal succinct representations of planar maps

ABSTRACT

This paper addresses the problem of representing the connectivity information of geometric objects using as little memory as possible. As opposed to raw compression issues, the focus is here on designing data structures that preserve the possibility of answering incidence queries in constant time. We propose in particular the first optimal representations for 3-connected planar graphs and triangulations, which are the most standard classes of graphs underlying meshes with spherical topology. Optimal means that these representations asymptotically match the respective entropy of the two classes, namely 2 bits per edge for 3-connected planar graphs, and 1.62 bits per triangle or equivalently 3.24 bits per vertex for triangulations.

REFERENCES

• 1: L. Castelli Aleardi, O. Devillers, and G. Schaeffer. Succinct representation of triangulations with a boundary. In Proc. of WADS, 134--145, 2005.
• 2: L. Castelli Aleardi, O. Devillers, and G. Schaeffer. Dynamic update of succinct triangulations. In Proc. of CCCG, pages 135-138, 2005.
• 3: P. Alliez and C. Gotsman. Recent advances in compression of 3d meshes. In N.A. Dodgson, M.S. Floater, and M.A. Sabin, editors, Advances in Multiresolution for Geometric Modelling, pages 3--26. Springer-Verlag, 2005.
• 4: Daniel K. Blandford , Guy E. Blelloch , Ian A. Kash, Compact representations of separable graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: J.-D. Boissonnat, O. Devillers, S. Pion, M. Teillaud, and M. Yvinec. Triangulations in CGAL. Comp. Geom.: Theory and Appl., 22:5--19, 2002.
• 6: Yi-Ting Chiang , Ching-Chi Lin , Hsueh-I Lu, Orderly spanning trees with applications to graph encoding and graph drawing, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.506-515, January 07-09, 2001, Washington, D.C., United States
• 7: Richie Chih-Nan Chuang , Ashim Garg , Xin He , Ming-Yang Kao , Hsueh-I Lu, Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.118-129, July 13-17, 1998
• 8: Éric Fusy , Dominique Poulalhon , Gilles Schaeffer, Dissections and trees, with applications to optimal mesh encoding and to random sampling, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Richard F. Geary , Rajeev Raman , Venkatesh Raman, Succinct ordinal trees with level-ancestor queries, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 10: M. Isenburg and J. Snoeyink. Graph Coding and Connectivity Compression. manuscript, 2004.
• 11: G. Jacobson. Space efficients static trees and graphs. In Proc. of FOCS, 549--554, 1989.
• 12: Kenneth Keeler , Jeffery Westbrook, Short encodings of planar graphs and maps, Discrete Applied Mathematics, v.58 n.3, p.239-252, April 7, 1995 [doi>10.1016/0166-218X(93)E0150-W ]
• 13: Andrei Khodakovsky , Pierre Alliez , Mathieu Desbrun , Peter Schröder, Near-optimal connectivity encoding of 2-manifold polygon meshes, Graphical Models, v.64 n.3/4, p.147-168, May/July 2002
• 14: Marcelo Kallmann , Daniel Thalmann, Star-vertices: a compact representation for planar meshes with adjacency information, Journal of Graphics Tools, v.6 n.1, p.7-18, September 2001
• 15: J. Ian Munro , Venkatesh Raman, Succinct Representation of Balanced Parentheses and Static Trees, SIAM Journal on Computing, v.31 n.3, p.762-776, 2001 [doi>10.1137/S0097539799364092]
• 16: J. Ian Munro , Venkatesh Raman , Adam J. Storm, Representing dynamic binary trees succinctly, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.529-536, January 07-09, 2001, Washington, D.C., United States
• 17: D. Poulalhon and G. Schaeffer. Optimal coding and sampling of triangulations. In Proc. of ICALP, 1080--1094, 2003.
• 18: Jarek Rossignac, Edgebreaker: Connectivity Compression for Triangle Meshes, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.47-61, January 1999 [doi>10.1109/2945.764870 ]
• 19: C. Touma and C. Gotsman. Triangle mesh compression. In Graphics Interface, pages 26--34, 1998.
• 20: G. Turan. Succinct representations of graphs. In Discr. and Appl. Math, pages 289--294, 1984.
• 21: W. Tutte. A census of planar triangulations. Canadian J. of Mathematics, 14:21--38, 1962.
• 22: W. Tutte. A census of planar maps. Canadian J. of Mathematics, 15:249--271, 1963.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms

Keywords:
compression, geometric data structures, graph encoding, mesh, planar maps, succinct data structures