## May 10, 2019:

#
Near-optimal compression for the planar graph metric

##
Pedro Matias

The Planar Graph Metric Compression Problem is to compactly encode the
distances among k nodes in a planar graph of size n. Two naïve solutions are
to store the graph using O(n) bits, or to explicitly store the distance
matrix with O(k2 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 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.
Our main result is a new compression of the planar graph metric into
$\tilde{O}(\min(k^2, \sqrt{k\dot n}))$ bits, which is optimal up to log
factors. Our data structure circumvents an $\tilde{O}(k^2)$ lower bound of
Krauthgamer, Nguyen, and Zondiner [SIDMA’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 Subset Distance
Oracle for planar graphs with $\tilde{O}(\sqrt{k\dot 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 labeling schemes in
planar graphs cannot be resolved with the current lower bound techniques. On
the positive side, we introduce the powerful tool of unit-monge to planar
graph algorithms.

(Based on a paper
by Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann [SODA 18])