Fast general methodology for information-theoretically optimal encodings of graphs
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 superadditive 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,..., l(1)} for l(1) less than or equal to n; (5) the edges of G are labeled with labels from {1,..., l(2)} for l(2) less than or equal to m; and (6) each node (respectively, edge) of G has at most l(3) = O(1) self-loops (respectively, l(4) = O(1) multiple edges). Moreover, l(3) and l(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.
planar graphs triangulations cycle separators data compression graph encoding triconnected graphs biconnected graphs