A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs

DOI10.1137/S0097539799359117zbMath0965.05090MaRDI QIDQ4507374

Hsueh-I Lu, Xin He, Ming-Yang Kao

Publication date: 18 October 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

data compressionplanar graphstriangulationsgraph encodingbiconnected graphstriconnected graphscycle separators

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Information theory (general) (94A15)

Related Items (12)

Graph compression and the zeros of polynomials ⋮ Building knowledge maps of web graphs ⋮ Succinct encoding of binary strings representing triangulations ⋮ A compact encoding of plane triangulations with efficient query supports ⋮ Tight and simple web graph compression for forward and reverse neighbor queries ⋮ Linear-time compression of 2-manifold polygon meshes into information-theoretically optimal number of bits ⋮ Quick encoding of plane graphs in \(\log _{2}14\) bits per edge ⋮ An edgebreaker-based efficient compression scheme for regular meshes ⋮ A Compact Encoding of Plane Triangulations with Efficient Query Supports ⋮ Fast and compact planar embeddings ⋮ Navigating planar topologies in near-optimal space and time ⋮ Linear-time algorithms for tree root problems

This page was built for publication: A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs