A Simple Distributed Deterministic Planar Separator
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917296016982016 |
|---|---|
| author | Abd-Elhaleem, Yaseen Dory, Michal Weimann, Oren |
| author_facet | Abd-Elhaleem, Yaseen Dory, Michal Weimann, Oren |
| contents | A balanced separator of a graph $G$ is a set of vertices whose removal disconnects the graph into connected components that are a constant factor smaller than $G$. Lipton and Tarjan [FOCS'77] famously proved that every planar graph admits a balanced separator of size $O(\sqrt{n})$, as well as a balanced separator of size $O(D)$ that is a simple path (where $D$ is $G$'s diameter). In the centralized setting, both separators can be found in linear time. In the distributed setting, $D$ is a universal lower bound for the round complexity of solving many optimization problems, so, separators of size $O(D)$ are preferable.
It was not until [DISC'17] that a distributed algorithm was devised by Ghaffari and Parter to compute such an $O(D)$-size separator in $\tilde O(D)$ rounds, by adapting the Lipton-Tarjan algorithm to the distributed model. Since then, this algorithm was used in several distributed algorithms for planar graphs, e.g., [GP, DISC'17], [LP, STOC'19], [AEDPW, PODC'25]. However, the algorithm is randomized, deeming the algorithms that use it to be randomized as well. Obtaining a deterministic algorithm remained an interesting open question until [PODC'25], when a (complex) deterministic separator algorithm was given by Jauregui, Montealegre and Rapaport.
We present a much simpler deterministic separator algorithm with the same (near-optimal) $\tilde O(D)$-round complexity. While previous works devised either complicated or randomized ways of transferring weights from vertices to faces of $G$, we show that a straightforward way also works: Each vertex simply transfers its weight to one arbitrary face it lies on. That's it!
We note that a deterministic separator algorithm directly derandomizes the state-of-the-art distributed algorithms for classical problems on planar graphs such as single-source shortest-paths, maximum-flow, directed global min-cut, and reachability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_22916 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Simple Distributed Deterministic Planar Separator Abd-Elhaleem, Yaseen Dory, Michal Weimann, Oren Distributed, Parallel, and Cluster Computing Data Structures and Algorithms A balanced separator of a graph $G$ is a set of vertices whose removal disconnects the graph into connected components that are a constant factor smaller than $G$. Lipton and Tarjan [FOCS'77] famously proved that every planar graph admits a balanced separator of size $O(\sqrt{n})$, as well as a balanced separator of size $O(D)$ that is a simple path (where $D$ is $G$'s diameter). In the centralized setting, both separators can be found in linear time. In the distributed setting, $D$ is a universal lower bound for the round complexity of solving many optimization problems, so, separators of size $O(D)$ are preferable. It was not until [DISC'17] that a distributed algorithm was devised by Ghaffari and Parter to compute such an $O(D)$-size separator in $\tilde O(D)$ rounds, by adapting the Lipton-Tarjan algorithm to the distributed model. Since then, this algorithm was used in several distributed algorithms for planar graphs, e.g., [GP, DISC'17], [LP, STOC'19], [AEDPW, PODC'25]. However, the algorithm is randomized, deeming the algorithms that use it to be randomized as well. Obtaining a deterministic algorithm remained an interesting open question until [PODC'25], when a (complex) deterministic separator algorithm was given by Jauregui, Montealegre and Rapaport. We present a much simpler deterministic separator algorithm with the same (near-optimal) $\tilde O(D)$-round complexity. While previous works devised either complicated or randomized ways of transferring weights from vertices to faces of $G$, we show that a straightforward way also works: Each vertex simply transfers its weight to one arbitrary face it lies on. That's it! We note that a deterministic separator algorithm directly derandomizes the state-of-the-art distributed algorithms for classical problems on planar graphs such as single-source shortest-paths, maximum-flow, directed global min-cut, and reachability. |
| title | A Simple Distributed Deterministic Planar Separator |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.22916 |