A compact encoding of plane triangulations with efficient query supports

DOI10.1016/J.IPL.2010.06.014MaRDI QIDQ407553zbMATH OpenOpenAlexFDO

Authors 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

plane triangulationencodingcoding schemequery support

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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)

Recommendations

• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
• Quick encoding of plane graphs in \(\log _{2}14\) bits per edge
• Succinct encoding of binary strings representing triangulations
• scientific article; zbMATH DE number 2038776

Cites work

• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 5506222 (Why is no real title available?)
• scientific article; zbMATH DE number 1962839 (Why is no real title available?)
• A Census of Planar Triangulations
• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
• Algorithms and Data Structures
• Balanced parentheses strike back
• Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
• On the succinct representation of graphs
• Optimal coding and sampling of triangulations
• Orderly Spanning Trees with Applications
• Orderly spanning trees with applications to graph encoding and graph drawing
• Short encodings of planar graphs and maps
• Succinct representation of balanced parentheses and static trees
• Succinct representations of planar maps

Cited in

(10)

• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• scientific article; zbMATH DE number 2038776 (Why is no real title available?)
• scientific article; zbMATH DE number 917638 (Why is no real title available?)
• Succinct encoding of binary strings representing triangulations
• A Compact Encoding of Rectangular Drawings with Efficient Query Supports
• Explicit Array-Based Compact Data Structures for Triangulations
• SCARST: Schnyder compact and regularity sensitive triangulation data structure
• Indexing graph search trees and applications
• Navigating planar topologies in near-optimal space and time
• Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings

Describes a project that uses

Uses Software

• Edgebreaker

This page was built for publication: A compact encoding of plane triangulations with efficient query supports

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