Succinct representations of planar maps

DOI10.1016/J.TCS.2008.08.016MaRDI QIDQ959810zbMATH OpenOpenAlexFDO

Authors 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

triangulationsdata compressionsuccinct data structuresgraph encodinggeometric data structuresplanar maps

Mathematics Subject Classification ID

Data structures (68P05) 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)

Recommendations

• Algorithms and Data Structures
• Succinct encoding of binary strings representing triangulations
• Navigating planar topologies in near-optimal space and time
• Succinct representations of separable graphs
• Explicit Array-Based Compact Data Structures for Triangulations

Cites work

• scientific article; zbMATH DE number 5506222 (Why is no real title available?)
• scientific article; zbMATH DE number 2147452 (Why is no real title available?)
• A Census of Planar Maps
• A Census of Planar Triangulations
• Algorithms and Data Structures
• Dissections and trees, with applications to optimal mesh encoding and to random sampling
• Lossless compression of predicted floating-point geometry
• Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes
• On the succinct representation of graphs
• Optimal coding and sampling of triangulations
• Orderly spanning trees with applications to graph encoding and graph drawing
• Representing dynamic binary trees succinctly
• Short encodings of planar graphs and maps
• Succinct ordinal trees with level-ancestor queries
• Succinct representation of balanced parentheses and static trees
• The enumeration of c-nets via quadrangulations
• Triangulations in CGAL

Cited in

(24)

• Algorithms and Data Structures
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• A compact encoding of plane triangulations with efficient query supports
• scientific article; zbMATH DE number 7765383 (Why is no real title available?)
• I/O and space-efficient path traversal in planar graphs
• Recent developments in floorplan representations
• Succinct representations of separable graphs
• Succinct representation of labeled graphs
• Succinct data structure for path graphs
• On the number of planar Eulerian orientations
• Succinct encodings for families of interval graphs
• Compact navigation and distance oracles for graphs with small treewidth
• Succinct and Implicit Data Structures for Computational Geometry
• Succinct encoding of binary strings representing triangulations
• A bijection for essentially 3-connected toroidal maps
• Catalog-based representation of 2D triangulations
• Succinct data structures for bounded clique-width graphs
• Succinct navigational oracles for families of intersection graphs on a circle
• Array-based compact data structures for triangulations: practical solutions with theoretical guarantees
• Succinct representation for (non)deterministic finite automata
• Implementing the topological model succinctly
• Dissections and trees, with applications to optimal mesh encoding and to random sampling
• I/O-efficient path traversal in succinct planar graphs
• Navigating planar topologies in near-optimal space and time

Describes a project that uses

Uses Software

• 2D triangulations
• Edgebreaker
• CGAL

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q959810)