  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.
