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

Xin He, Ming Yang Kao, Hsueh I. Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. The methodology is applicable to general classes of graphs; this paper focuses on simple planar graphs. Specifically, a graph with property π is called a π-graph.If π satisfies certain properties, then an n-node π-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 function β(n) = Ω{n) so that there are at most 2β(n)+o(β (n)) distinct n-node n-graphs. Examples of such n include all conjunctions of the following sets 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; and (4) G has at most ℓ1 (respectively, ℓ2) distinct node (respectively, edge) labels. These examples are novel applications of small cycle separators of planar graphs and settle several problems that have been open since Tutte's census series were published in 1960's.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 1999 - 7th Annual European Symposium, Proceedings
EditorsJaroslav Nešetřil
PublisherSpringer Verlag
Pages540-549
Number of pages10
ISBN (Print)3540662510, 9783540662518
DOIs
StatePublished - Jan 1 1999
Event7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic
Duration: Jul 16 1999Jul 18 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1643
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th Annual European Symposium on Algorithms, ESA 1999
CountryCzech Republic
CityPrague
Period7/16/997/18/99

Fingerprint

Encoding
Methodology
Graph in graph theory
Separators
Planar graph
Labels
Vertex of a graph
Distinct
Property of set
Plane Graph
Separator
Census
Simple Graph
Strings
Binary
Cycle
Series

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

He, X., Kao, M. Y., & Lu, H. I. (1999). A fast general methodology for information — theoretically optimal encodings of graphs. In J. Nešetřil (Ed.), Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings (pp. 540-549). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643). Springer Verlag. https://doi.org/10.1007/3-540-48481-7_47
He, Xin ; Kao, Ming Yang ; Lu, Hsueh I. / A fast general methodology for information — theoretically optimal encodings of graphs. Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. editor / Jaroslav Nešetřil. Springer Verlag, 1999. pp. 540-549 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{3b9d77b16c0142c4892813502873cc50,
title = "A fast general methodology for information — theoretically optimal encodings of graphs",
abstract = "We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. The methodology is applicable to general classes of graphs; this paper focuses on simple planar graphs. Specifically, a graph with property π is called a π-graph.If π satisfies certain properties, then an n-node π-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 function β(n) = Ω{n) so that there are at most 2β(n)+o(β (n)) distinct n-node n-graphs. Examples of such n include all conjunctions of the following sets 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; and (4) G has at most ℓ1 (respectively, ℓ2) distinct node (respectively, edge) labels. These examples are novel applications of small cycle separators of planar graphs and settle several problems that have been open since Tutte's census series were published in 1960's.",
author = "Xin He and Kao, {Ming Yang} and Lu, {Hsueh I.}",
year = "1999",
month = "1",
day = "1",
doi = "10.1007/3-540-48481-7_47",
language = "English (US)",
isbn = "3540662510",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "540--549",
editor = "Jaroslav Nešetřil",
booktitle = "Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings",
address = "Germany",

}

He, X, Kao, MY & Lu, HI 1999, A fast general methodology for information — theoretically optimal encodings of graphs. in J Nešetřil (ed.), Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1643, Springer Verlag, pp. 540-549, 7th Annual European Symposium on Algorithms, ESA 1999, Prague, Czech Republic, 7/16/99. https://doi.org/10.1007/3-540-48481-7_47

A fast general methodology for information — theoretically optimal encodings of graphs. / He, Xin; Kao, Ming Yang; Lu, Hsueh I.

Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. ed. / Jaroslav Nešetřil. Springer Verlag, 1999. p. 540-549 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

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

AU - He, Xin

AU - Kao, Ming Yang

AU - Lu, Hsueh I.

PY - 1999/1/1

Y1 - 1999/1/1

N2 - We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. The methodology is applicable to general classes of graphs; this paper focuses on simple planar graphs. Specifically, a graph with property π is called a π-graph.If π satisfies certain properties, then an n-node π-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 function β(n) = Ω{n) so that there are at most 2β(n)+o(β (n)) distinct n-node n-graphs. Examples of such n include all conjunctions of the following sets 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; and (4) G has at most ℓ1 (respectively, ℓ2) distinct node (respectively, edge) labels. These examples are novel applications of small cycle separators of planar graphs and settle several problems that have been open since Tutte's census series were published in 1960's.

AB - We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. The methodology is applicable to general classes of graphs; this paper focuses on simple planar graphs. Specifically, a graph with property π is called a π-graph.If π satisfies certain properties, then an n-node π-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 function β(n) = Ω{n) so that there are at most 2β(n)+o(β (n)) distinct n-node n-graphs. Examples of such n include all conjunctions of the following sets 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; and (4) G has at most ℓ1 (respectively, ℓ2) distinct node (respectively, edge) labels. These examples are novel applications of small cycle separators of planar graphs and settle several problems that have been open since Tutte's census series were published in 1960's.

UR - http://www.scopus.com/inward/record.url?scp=84958059248&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958059248&partnerID=8YFLogxK

U2 - 10.1007/3-540-48481-7_47

DO - 10.1007/3-540-48481-7_47

M3 - Conference contribution

AN - SCOPUS:84958059248

SN - 3540662510

SN - 9783540662518

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 540

EP - 549

BT - Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings

A2 - Nešetřil, Jaroslav

PB - Springer Verlag

ER -

He X, Kao MY, Lu HI. A fast general methodology for information — theoretically optimal encodings of graphs. In Nešetřil J, editor, Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Springer Verlag. 1999. p. 540-549. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-48481-7_47