Abstract
We present nearly optimal distributed algorithms for fundamental reachability problems in planar graphs. In the singlesource reachability problem given is an nvertex directed graph G = (V,E) and a source node s, it is required to determine the subset of nodes that are reachable from s in G. We present the first distributed reachability algorithm for planar graphs that runs in nearly optimal time of Õ(D) rounds, where D is the undirected diameter of the graph. This improves the complexity of Õ(D²) rounds implied by the recent work of [Li and Parter, STOC'19].
We also consider the more general reachability problem of identifying the strongly connected components (SCCs) of the graph. We present an Õ(D)round algorithm that computes for each node in the graph an identifier of its strongly connected component in G. No nontrivial upper bound for this problem (even in general graphs) has been known before.
Our algorithms are based on characterizing the structural interactions between balanced cycle separators. We show that the reachability relations between separator nodes can be compressed due to a Mongelike property of their directed shortest paths. The algorithmic results are obtained by combining this structural characterization with the recursive graph partitioning machinery of [Li and Parter, STOC'19].
BibTeX  Entry
@InProceedings{parter:LIPIcs:2020:13116,
author = {Merav Parter},
title = {{Distributed Planar Reachability in Nearly Optimal Time}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {38:138:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771689},
ISSN = {18688969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13116},
URN = {urn:nbn:de:0030drops131160},
doi = {10.4230/LIPIcs.DISC.2020.38},
annote = {Keywords: Distributed Graph Algorithms, Planar Graphs, Reachability}
}
Keywords: 

Distributed Graph Algorithms, Planar Graphs, Reachability 
Collection: 

34th International Symposium on Distributed Computing (DISC 2020) 
Issue Date: 

2020 
Date of publication: 

07.10.2020 