Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs
Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, Julian Werthmann · 2023
We consider the problem of computing a compact routing scheme for a weighted undirected planar graph G := (V, E, w) in several models. For a given parameter ϵ > 0, we compute a routing scheme with stretch 1 + ϵ and labels and routing tables of size Õ(ϵ−1). In CONGEST, the construction takes Õ(ϵ−3 · HD) time, where HD denotes the network's hop-diameter. Further, it takes Õ(ϵ−3) time in a PRAM with O(n) processors and the novel HYBRID model. Thus, our algorithms are almost optimal in all relevant parameters. To achieve these results, we extend the divide-and-conquer framework of Li and Parter [STOC '19] and combine it with state-of-the-art distributed distance approximation algorithms [STOC '22].