A compact encoding of plane triangulations with efficient query supports

DOI10.1016/j.ipl.2010.06.014zbMath1234.68102MaRDI 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

encoding; plane triangulation; coding scheme; query support

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

05C85: Graph algorithms (graph-theoretic aspects)

Uses Software

• Edgebreaker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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