Near-Optimal Compression for the Planar Graph Metric
Preprint
Abstract
The Planar Graph Metric Compression Problem is to compactly encode the distances among $k$ nodes in a planar graph of size $n$. Two na\"ive 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, Prennes, and Raz [SODA'01], who rule out compressions into a polynomially smaller number of bits, for {\em 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 labelling schemes, dynamic algorithms, and compact routing. Our main result is a new compression of the planar graph metric into $\tilde{O}(\min (k^2 , \sqrt{k\cdot n}))$ bits, which is optimal up to log factors. Our data structure breaks an $\Omega(k^2)$ lower bound of Krauthgamer, Nguyen, and Zondiner [SICOMP'14] for compression using minors, and the lower bound of Gavoille et al. for compression of weighted planar graphs. This is an unexpected and decisive proof that weights can make planar graphs inherently more complex. Moreover, we design a new {\em Subset Distance Oracle} for planar graphs with $\tilde O(\sqrt{k\cdot n})$ space, and $\tilde O(n^{3/4})$ query time. Our work carries strong messages to related fields. In particular, the famous $O(n^{1/2})$ vs. $\Omega(n^{1/3})$ gap for distance labelling schemes in planar graphs {\em cannot} be resolved with the current lower bound techniques.
Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search2015
- Many Distances in Planar GraphsAlgorithmica, 2010
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time2010
- Semi-local String Comparison: Algorithmic Techniques and ApplicationsMathematics in Computer Science, 2008
- Distance labeling in graphsJournal of Algorithms, 2004
- Compact and localized distributed data structuresDistributed Computing, 2003
- Database-friendly random projections: Johnson-Lindenstrauss with binary coinsJournal of Computer and System Sciences, 2003
- Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential AlgorithmsAlgorithmica, 2000
- Planar spanners and approximate shortest path queries among obstacles in the plane1996
- Geometric applications of a matrix-searching algorithmAlgorithmica, 1987