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

DOI10.1137/S0097539799359117MaRDI QIDQ4507374zbMATH OpenFDO

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

Publication date 18 October 2000

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

zbMATH Keywords

triangulationsdata compressionplanar graphsgraph encodingbiconnected graphstriconnected graphscycle separators

Mathematics Subject Classification ID

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

Recommendations

• On the succinct representation of graphs
• Short encodings of planar graphs and maps
• An Information-Theoretic Upper Bound on Planar Graphs Using Well-Orderly Maps
• Quick encoding of plane graphs in \(\log _{2}14\) bits per edge
• Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings

Cited in

(22)

• An edgebreaker-based efficient compression scheme for regular meshes
• Succinct planar encoding with minor operations
• scientific article; zbMATH DE number 1440644 (Why is no real title available?)
• Graph compression and the zeros of polynomials
• scientific article; zbMATH DE number 1962839 (Why is no real title available?)
• A compact encoding of plane triangulations with efficient query supports
• Linear-time algorithms for tree root problems
• Linear-time compression of 2-manifold polygon meshes into information-theoretically optimal number of bits
• Maximum information stored in a labeled connected network with minimum edges
• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• Quick encoding of plane graphs in \(\log _{2}14\) bits per edge
• scientific article; zbMATH DE number 1988012 (Why is no real title available?)
• Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
• Building knowledge maps of web graphs
• Space-efficient graph coarsening with applications to succinct planar encodings
• Planar graphs, via well-orderly maps and trees
• Succinct encoding of binary strings representing triangulations
• Graph-Theoretic Concepts in Computer Science
• Information theoretic measures of UHG graphs with low computational complexity
• Tight and simple web graph compression for forward and reverse neighbor queries
• Navigating planar topologies in near-optimal space and time
• scientific article; zbMATH DE number 2032369 (Why is no real title available?)

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

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