Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits

摘要

This extended abstract summarizes a new result for the graphcompression problem, addressing how to compress a graphG into a binary string Z with the requirement thatZ can be decoded to recover G. Graphcompression finds important applications in 3D model compression ofComputer Graphics [12, 17-20] and compact routing table of ComputerNetworks [7]. For brevity, let a ¦Ð-graph standfor a graph with property ¦Ð. Theinformation-theoretically optimal number of bits required torepresent an n-node ¦Ð-graph is⌈log₂N_¦Ð(n)⌉, whereN_¦Ð(n) is the number ofdistinct n-node ¦Ð-graphs. Although determiningor approximating the close forms ofN_¦Ð(n) for nontrivial classesof ¦Ð is challenging, we provide a linear-timemethodology for graph compressionschemes that areinformation-theoretically optimal with respect to continuoussuper-additive functions (abbreviated as optimal for therest of the extended abstract). Specifically, if ¦Ðsatisfies certain properties, then we can compress anyn-node m-edge ¦Ð-graph G into abinary string Z such that G and Z can becomputed from each other in O(m + n) time, and thatthe bit count of Z is at most ¦A(n) +o(¦A(n)) for any continuoussuper-additive function ¦A(n) withlog₂N_¦Ð(n)¡U ¦A(n) +o(¦A(n)). Our methodology is applicableto general classes of graphs; this extended abstract focuses ongraphs with sublinear genus. For example, if the inputn-node ¦Ð-graph G is equipped with anembedding on its genus surface, which is a reasonable assumptionfor graphs arising from3D model compression, then our methodologyis applicable to any ¦Ð satisfying the followingstatements:

F1. The genus of any n-node ¦Ð-graph iso(n/log² n);

F2. Any subgraph of a ¦Ð-graph remains a¦Ð-graph;

F3. log N _¦Ð(n) =¦¸(n); and

F4. There is an integer k = O(1) such that ittakes O(n) time to determine whether anO(log^(k) n)-node graph satisfiesproperty ¦Ð.

For instance, ¦Ð can be the property of being adirected 3-colorable simple graph with genus no more than ten. Theresult is a novel application of planarization algorithm forbounded-genus graphs [5] and separator decomposition tree of planargraphs [9]. Rooted trees were the only known nontrivial class ofgraphs with linear-time optimal coding schemes. He, Kao, and Lu[11] provided O(n log n)-time compressionschemes for planar and plane graphs that are optimal. Our resultssignificantly enlarge the classes of graphs that admit efficientoptimal compression schemes. More results on various versions ofgraph compression problems or succinct graph representations can befound in [1-4, 6, 8, 10, 14, 15] and the references therein.