A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
| dc.creator | He, Xin | |
| dc.creator | Kao, Ming-Yang | |
| dc.creator | Lu, Hsueh-I | |
| dc.date | 2001-01-23 | |
| dc.date.accessioned | 2026-07-07T03:16:52Z | |
| dc.date.available | 2026-07-07T03:16:52Z | |
| dc.description | We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property pi is called a pi-graph. If pi satisfies certain properties, then an n-node m-edge pi-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 beta(n)+o(beta(n)) bits for any continuous super-additive function beta(n) so that there are at most 2^{beta(n)+o(beta(n))} distinct n-node pi-graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such pi 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, ..., ell_1} for ell_1 <= n; (5) the edges of G are labeled with labels from {1, ..., ell_2} for ell_2 <= m; and (6) each node (respectively, edge) of G has at most ell_3 = O(1) self-loops (respectively, ell_4 = O(1) multiple edges). Moreover, ell_3 and ell_4 are not required to be O(1) for the cases of pi 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0101021 | |
| dc.identifier | http://arxiv.org/abs/cs/0101021 | |
| dc.identifier | SIAM Journal on Computing, 30(3):838--846, 2000 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30516 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Graphics | |
| dc.subject | E.4; F.2.2 | |
| dc.title | A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs | |
| dc.type | text |