Deterministic Distributed DFS via Cycle Separators in Planar Graphs

One of the most basic techniques in algorithm design consists of breaking a problem into subproblems and then proceeding recursively. In the case of graph algorithms, one way to implement this approach is through separator sets. Given a graph G = (V, E), a subset of nodes S ⊆ V is called a separator set of G if the size of each connected component of G - S is at most 2/3 · |V|. The most useful separator sets are those that satisfy certain restrictions of cardinality or structure.In this work, we present the first deterministic algorithm in the distributed CONGEST model that recursively computes a cycle separator over planar graphs in O(D) rounds. This result, as in the centralized setting, has significant implications in the area of distributed planar algorithms. In fact, from this result, we can construct a deterministic algorithm that computes a DFS tree in O(D) rounds. This matches both the best-known randomized algorithm of Ghaffari and Parter (DISC, 2017) and, up to polylogarithmic factors, the trivial lower bound of ω(D) rounds.