Planar Diameter via Metric Compression

We develop a new approach for distributed distance computation in planar graphs that is based on a variant of the metric compression problem recently introduced by Abboud et al. [SODA'18]. In our variant of the Planar Graph Metric Compression Problem, one is given an n-vertex planar graph G = (V, E), a set of S subset of V source terminals lying on a single face, and a subset of target terminals T subset of V. The goal is to compactly encode the S x T distances.

One of our key technical contributions is in providing a compression scheme that encodes all S x T distances using (O) over tilde(vertical bar S vertical bar center dot poly(D)+ vertical bar T vertical bar) bits, for unweighted graphs with diameter D. This significantly improves the state of the art of (O) over tilde(vertical bar S vertical bar . 2(D) + vertical bar T vertical bar . D) bits. We also consider an approximate version of the problem for weighted graphs, where the goal is to encode (1 + epsilon) approximation of the S x T distances, for a given input parameter epsilon is an element of (0, 1]. Here, our compression scheme uses (O) over tilde (poly(vertical bar S vertical bar/epsilon) + vertical bar T vertical bar) bits. In addition, we describe how these compression schemes can be computed in near-linear time. At the heart of this compact compression scheme lies a VC-dimension type argument on planar graphs, using the well-known SaueraAZ's lemma.

This efficient compression scheme leads to several improvements and simplifications in the setting of diameter computation, most notably in the distributed setting:

There is an (O) over tilde (D-5)-round randomized distributed algorithm for computing the diameter in planar graphs, w.h.p.

There is an (O) over tilde (D-3) + D(2)poly(log n/epsilon)-round randomized distributed algorithm for computing a (1+epsilon) approximation for the diameter in weighted planar graphs, with unweighted diameter D, w.h.p.

No sublinear round algorithms were known for these problems before. These distributed constructions are based on a new recursive graph decomposition that preserves the (unweighted) diameter of each of the subgraphs up to a logarithmic term. Using this decomposition, we also get an exact SSSP tree computation within e (O) over tilde (D-2) rounds.