Succinct representations of planar maps

DOI10.1016/j.tcs.2008.08.016zbMath1157.68066OpenAlexW2024465063MaRDI QIDQ959810

L. Castelli Aleardi, Gilles Schaeffer, Olivier Devillers

Publication date: 12 December 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.016

zbMATH Keywords

data compressiontriangulationsplanar mapssuccinct data structuresgraph encodinggeometric data structures

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (18)

CATALOG-BASED REPRESENTATION OF 2D TRIANGULATIONS ⋮ Schnyder woods for higher genus triangulated surfaces, with applications to encoding ⋮ On the number of planar Eulerian orientations ⋮ Succinct encodings for families of interval graphs ⋮ Succinct encoding of binary strings representing triangulations ⋮ A compact encoding of plane triangulations with efficient query supports ⋮ Succinct representation of labeled graphs ⋮ Succinct data structure for path graphs ⋮ Unnamed Item ⋮ Recent Developments in Floorplan Representations ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ I/O-efficient path traversal in succinct planar graphs ⋮ A bijection for essentially 3-connected toroidal maps ⋮ Fast and compact planar embeddings ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Succinct representation for (non)deterministic finite automata ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ Navigating planar topologies in near-optimal space and time

Uses Software

• CGAL
• Edgebreaker
• 2D triangulations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lossless compression of predicted floating-point geometry
• On the succinct representation of graphs
• Optimal coding and sampling of triangulations
• Triangulations in CGAL
• Short encodings of planar graphs and maps
• Succinct Representation of Balanced Parentheses and Static Trees
• Succinct ordinal trees with level-ancestor queries
• A Census of Planar Triangulations
• Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes
• Algorithms and Data Structures
• The enumeration of c-nets via quadrangulations
• A Census of Planar Maps

This page was built for publication: Succinct representations of planar maps