Linear-Time Compression of Bounded-Genus Graphs into Information-Theoretically Optimal Number of Bits

DOI10.1137/120879142zbMath1092.68612arXiv1401.2538OpenAlexW3105127893MaRDI QIDQ4828935

Hsueh-I Lu

Publication date: 29 November 2004

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

Full work available at URL: https://arxiv.org/abs/1401.2538

zbMATH Keywords

planar graphscompressiondata structuresgraph algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

Graph compression and the zeros of polynomials, 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

Uses Software

• Edgebreaker