Distributed algorithms for planar networks I: Planar embedding

M Ghaffari, B Haeupler - Proceedings of the 2016 ACM Symposium on …, 2016 - dl.acm.org
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016dl.acm.org
This paper presents the first (non-trivial) distributed planar embedding algorithm. We
consider this a crucial first step in a broader program to design efficient distributed
algorithms for planar networks. We work in the standard distributed model in which nodes
can send an O (log n)-bit message to each of their neighbors per round. In a planar network,
with n nodes and diameter D, our deterministic planar embedding algorithm uses O (D dot
min {log n, D) rounds to compute a combinatorial planar embedding, which consists of each …
This paper presents the first (non-trivial) distributed planar embedding algorithm. We consider this a crucial first step in a broader program to design efficient distributed algorithms for planar networks. We work in the standard distributed model in which nodes can send an O(log n)-bit message to each of their neighbors per round. In a planar network, with n nodes and diameter D, our deterministic planar embedding algorithm uses O(D dot min{log n, D) rounds to compute a combinatorial planar embedding, which consists of each node knowing the clockwise order of its incident edges in a fixed planar drawing. The complexity of our algorithm is near-optimal and matches the trivial lower bound of Omega(D) up to a log n factor. No algorithm outperforming the trivial round complexity of O(n) was known prior to this work.
ACM Digital Library