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 ⊆ V source terminals lying on a single face, and a subset of target terminals T ⊆ V . The goal is to compactly encode the S × T distances. One of our key technical contributions is in providing a compression scheme that encodes all S × T distances using O (| S |·( D )+| T |) bits, for unweighted graphs with diameter D . This significantly improves the state of the art of O (| S |· 2 D +| T | · D ) bits. We also consider an approximate version of the problem for weighted graphs, where the goal is to encode (1+є) approximation of the S × T distances, for a given input parameter є ∈ (0,1]. Here, our compression scheme uses O ((| S |/є)+| T |) 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 Sauer’’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 ( D 5 )-round randomized distributed algorithm for computing the diameter in planar graphs, w.h.p. There is an O ( D 3 )+ D 2 (log n /є)-round randomized distributed algorithm for computing a (1+є) 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 O ( D 2 ) rounds.

Authors

• Jason Li 0006
• Merav Parter

Keywords

• diameter
• distributed computing
• metric compression
• planar graphs
• shortest path