Near-Optimal Compression for the Planar Graph Metric

26/04/2018 - 12:00

The Planar Graph Metric Compression Problem is to compactly encode the distances among $k$ nodes in a planar graph of size $n$. Two naive solutions are to store the graph using $O(n)$ bits, or to explicitly store the distance matrix with $O(k^2 \log{n})$ bits. The only lower bounds are from the seminal work of Gavoille, Peleg, Pérennes, and Raz [SODA'01], who rule out compressions into a polynomially smaller number of bits, for \emph{weighted} planar graphs, but leave a large gap for unweighted planar graphs. For example, when $k=\sqrt{n}$, the upper bound is $O(n)$ and their constructions imply an $\Omega(n^{3/4})$ lower bound. This gap is directly related to other major open questions in labeling schemes, dynamic algorithms, and compact routing.