Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits
Hsueh-I Lu · 2002
1 I n t roduct ion This extended abstract summarizes a new result for the graph compression problem, addressing how to compress a graph G into a binary string Z with the requirement that Z can be decoded to recover G. Graph compression finds important applications in 3D model compression of Computer Graphics [12, 17-20] and compact routing ta-ble of Computer Networks [7}. For brevity, let a ~r-graph stand for a graph with property n. The information-theoretically optimal number of bits required to repre-sent an n-node n-graph is [log 2 N~(n)], where N,~(n) is the number of distinct n-node *r-graphs. Although determining or approximating the close forms of N ~ (n) for nontrivial classes of n is challenging, we provide a linear-time methodology for graph compression schemes that are information-theoretically optimal with respect to continuous uper-additive functions (abbreviated as optimal for the rest of the extended abstract). 1 Specifi-cally, if 7r satisfies certain properties, then we can com-press any n-node m-edge 1r-graph G into a binary string Z such that G and Z can be computed from each other in O(m + n) time, and that the bit count of Z is at most fl(n) + o(fl(n)) for any continuous uper-additive function fl(n) with log 2 N~(n) < fl(n) + o(fl(n)). Our methodology is applicable to general classes of graphs; this extended abstract focuses on graphs with sublinear genus. 2 For example, if the input n-node,r-graph G is equipped with an embedding on its genus surface, which is a reasonable assumption for graphs arising from 3D model compression, then our methodology is applicable to any 7r satisfying the following statements: