A compact encoding of plane triangulations with efficient query supports

DOI10.1016/j.ipl.2010.06.014zbMath1234.68102OpenAlexW2074087808MaRDI QIDQ407553

Katsuhisa Yamanaka, Shin-ichi Nakano

Publication date: 27 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2115/48327

zbMATH Keywords

encodingplane triangulationcoding schemequery support

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Succinct encoding of binary strings representing triangulations ⋮ Unnamed Item ⋮ Fast and compact planar embeddings ⋮ Navigating planar topologies in near-optimal space and time

Uses Software

• Edgebreaker

Cites Work

• On the succinct representation of graphs
• Optimal coding and sampling of triangulations
• Succinct representations of planar maps
• Short encodings of planar graphs and maps
• Succinct Representation of Balanced Parentheses and Static Trees
• A Census of Planar Triangulations
• A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
• Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
• Balanced parentheses strike back
• Orderly Spanning Trees with Applications
• Algorithms and Data Structures
• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item