A fast general methodology for information-theoretically optimal encodings of graphs

Xin He*, Ming Yang Kao, Hsueh I. Lu

*Corresponding author for this work

Research output: Contribution to journalArticle

39 Scopus citations

Abstract

We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property π is called a π-graph. If π satisfies certain properties, then an n-node m-edge π-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most β(n)+o(β(n)) bits for any continuous superadditive function β(n) so that there are at most 2β(n)+o(β(n)) distinct n-node π-graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such π include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from {1, . . . , ℓ1} for ℓ1 ≤ n; (5) the edges of G are labeled with labels from {1, . . . , ℓ2} for ℓ2 ≤ m; and (6) each node (respectively, edge) of G has at most ℓ3 = O(1) self-loops (respectively, ℓ4 = O(1) multiple edges). Moreover, ℓ3 and ℓ4 are not required to be O(1) for the cases of π being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes.

Original languageEnglish (US)
Pages (from-to)838-846
Number of pages9
JournalSIAM Journal on Computing
Volume30
Issue number3
DOIs
StatePublished - Jan 1 2000

Keywords

  • Biconnected graphs
  • Cycle separators
  • Data compression
  • Graph encoding
  • Planar graphs
  • Triangulations
  • Triconnected graphs

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A fast general methodology for information-theoretically optimal encodings of graphs'. Together they form a unique fingerprint.

  • Cite this