research-article

Distributed Algorithms for Planar Networks I: Planar Embedding

Authors:

Mohsen Ghaffari,

Bernhard HaeuplerAuthors Info & Claims

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Pages 29 - 38

https://doi.org/10.1145/2933057.2933109

Published: 25 July 2016 Publication History

Abstract

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.

References

[1]

Kellogg S Booth and George S Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13(3):335--379, 1976.

Digital Library

[2]

John M Boyer and Wendy J Myrvold. On the cutting edge: Simplified O (n) planarity by edge addition. J. Graph Algorithms Appl., 8(2):241--273, 2004.

[3]

Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn. Distributed connectivity decomposition. In the Proc.\ of the Int'l Symp.\ on Princ.\ of Dist.\ Comp.\ (PODC), pages 156--165, 2014.

Digital Library

[4]

Erik Demaine, Shay Mozes, Christian Sommer, and Siamak Tazari. Algorithms for planar graphs and beyond. http://courses.csail.mit.edu/6.889/fall11/. Accessed: July 2015.

[5]

1}DasSarma-11Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In Proc.\ of the Symp.\ on Theory of Comp.\ (STOC), pages 363--372, 2011.

Digital Library

[6]

Jack Edmonds. A combinatorial representation of polyhedral surfaces. Notices of the American Mathematical Society, 7, 1960.

[7]

Michael Elkin. A faster distributed protocol for constructing a minimum spanning tree. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 359--368. Society for Industrial and Applied Mathematics, 2004.

Digital Library

[8]

Michael Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In Proc.\ of the Symp.\ on Theory of Comp.\ (STOC), pages 331--340, 2004.

Digital Library

[9]

Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks II: Low-congestion shortcuts, mst, and min-cut. In Pro.\ of ACM-SIAM Symp.\ on Disc.\ Alg.\ (SODA), page to appear, 2016.

Digital Library

[10]

Mohsen Ghaffari. Near-optimal distributed approximation of minimum-weight connected dominating set. In the Proc. of the Int'l Colloquium on Automata, Languages and Programming (ICALP), 2014.

[11]

Mohsen Ghaffari and Fabian Kuhn. Distributed minimum cut approximation. In Proc.\ of the Int'l Symp.\ on Dist.\ Comp.\ (DISC), pages 1--15, 2013.

Digital Library

[12]

5}Flow15Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir. Near-optimal distributed maximum flow. In the Proc.\ of the Int'l Symp.\ on Princ.\ of Dist.\ Comp.\ (PODC), 2015.

Digital Library

[13]

Mohsen Ghaffari and Christoph Lenzen. Near-optimal distributed tree embedding. In Proc.\ of the Int'l Symp.\ on Dist.\ Comp.\ (DISC), pages 197--211, 2014.

[14]

John Hopcroft and Robert Tarjan. Efficient planarity testing. Journal of the ACM (JACM), 21(4):549--568, 1974.

Digital Library

[15]

Bernhard Haeupler and Robert E Tarjan. Planarity algorithms via PQ-trees. Electronic Notes in Discrete Mathematics, 31:143--149, 2008.

[16]

Philip Klein. Topics in algorithms: Planar graph algorithms. http://cs.brown.edu/courses/csci2950-r/. Accessed: July 2015.

[17]

Philip Klein and Claire Mathieu. Optimization algorithms for planar graphs. http://cs.brown.edu/courses/cs250/. Accessed: July 2015.

[18]

Philip Klein and Shay Mozes. Optimization Algorithms for Planar Graphs. http://www.planarity.org/, draft.

[19]

Shay Kutten and David Peleg. Fast distributed construction of k-dominating sets and applications. In the Proc.\ of the Int'l Symp.\ on Princ.\ of Dist.\ Comp.\ (PODC), pages 238--251, 1995.

Digital Library

[20]

Philip N Klein and John H Reif. An efficient parallel algorithm for planarity. Journal of Computer and System Sciences, 37(2):190--246, 1988.

Digital Library

[21]

Abraham Lempel, Shimon Even, and Israel Cederbaum. An algorithm for planarity testing of graphs. Theory of graphs, 8(2):215--232, 1966.

[22]

Christoph Lenzen and Boaz Patt-Shamir. Fast routing table construction using small messages: Extended abstract. In Proc.\ of the Symp.\ on Theory of Comp.\ (STOC), pages 381--390, 2013.

Digital Library

[23]

Christoph Lenzen and Boaz Patt-Shamir. Improved distributed steiner forest construction. In the Proc.\ of the Int'l Symp.\ on Princ.\ of Dist.\ Comp.\ (PODC), pages 262--271, 2014.

Digital Library

[24]

Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177--189, 1979.

Digital Library

[25]

Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proc.\ of the Symp.\ on Theory of Comp.\ (STOC), pages 565--573, 2014.

Digital Library

[26]

Takao Nishizeki and Norishige Chiba. Planar graphs: Theory and algorithms. Elsevier, 1988.

[27]

Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms. In Proc.\ of the Int'l Symp.\ on Dist.\ Comp.\ (DISC), pages 439--453, 2014.

[28]

David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

Digital Library

[29]

David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed MST construction. In Proc.\ of the Symp.\ on Found.\ of Comp.\ Sci.\ (FOCS), pages 253--, 1999.

Digital Library

Cited By

Bousquet NFeuilloley LPierron T(2024)Local certification of graph decompositions and applications to minor-free classesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104954(104954)Online publication date: Jul-2024
https://doi.org/10.1016/j.jpdc.2024.104954
Augustine JMoses WPandurangan G(2024)Awake Complexity of Distributed Minimum Spanning TreeStructural Information and Communication Complexity10.1007/978-3-031-60603-8_3(45-63)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_3
Chang YOshman RNolin AHalldorsson MBalliu A(2023)Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their ApplicationsProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594604(55-66)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594604
Show More Cited By

Index Terms

Distributed Algorithms for Planar Networks I: Planar Embedding
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms
    2. Graph algorithms analysis

Recommendations

Polylogarithmic-time deterministic network decomposition and distributed derandomization
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated 2^O(√logn)-time algorithm of Panconesi and Srinivasan [STOC’92] and settles a central and long-standing question in ...
An optimal distributed (Δ+1)-coloring algorithm?
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log^∗n + Det_d(poly logn)) time, where Det_d(n′) ...
Optimal distributed covering algorithms
Abstract
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is ... $^{}$ $^{}$ $_{}$
$\begin{matrix} ((\frac{}{}^{}^{}^{})) \end{matrix}$
$\{_{}\}$ $_{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

July 2016

508 pages

ISBN:9781450339643

DOI:10.1145/2933057

General Chair:
George Giakkoupis
INRIA, France

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Conference

PODC '16

Sponsor:

PODC '16: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2016

Illinois, Chicago, USA

Acceptance Rates

PODC '16 Paper Acceptance Rate 40 of 149 submissions, 27%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
256
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bousquet NFeuilloley LPierron T(2024)Local certification of graph decompositions and applications to minor-free classesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104954(104954)Online publication date: Jul-2024
https://doi.org/10.1016/j.jpdc.2024.104954
Augustine JMoses WPandurangan G(2024)Awake Complexity of Distributed Minimum Spanning TreeStructural Information and Communication Complexity10.1007/978-3-031-60603-8_3(45-63)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_3
Chang YOshman RNolin AHalldorsson MBalliu A(2023)Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their ApplicationsProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594604(55-66)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594604
Chang HConroy JLe HMilenkovic LSolomon SThan C(2023)Covering Planar Metrics (and Beyond): O(1) Trees Suffice2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00139(2231-2261)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00139
Feuilloley LFraigniaud PMontealegre PRapaport IRémila ÉTodinca I(2023)Local certification of graphs with bounded genusDiscrete Applied Mathematics10.1016/j.dam.2022.10.004325(9-36)Online publication date: Jan-2023
https://doi.org/10.1016/j.dam.2022.10.004
Chang YSu HMilani AWoelfel P(2022)Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander DecompositionsProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538423(301-312)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538423
Izumi TKitamura NNaruse TSchwartzman GAgrawal KLee I(2022)Fully Polynomial-Time Distributed Computation in Low-Treewidth GraphsProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538590(11-22)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538590
Ghaffari MHaeupler BMiller ACensor-Hillel K(2021)Low-Congestion Shortcuts for Graphs Excluding Dense MinorsProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467935(213-221)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467935
Chang YPettie SSaranurak TZhang H(2021)Near-optimal Distributed Triangle Enumeration via Expander DecompositionsJournal of the ACM10.1145/344633068:3(1-36)Online publication date: 13-May-2021
https://dl.acm.org/doi/10.1145/3446330
Feuilloley LFraigniaud PMontealegre PRapaport IRémila ÉTodinca I(2021)Compact Distributed Certification of Planar GraphsAlgorithmica10.1007/s00453-021-00823-wOnline publication date: 6-May-2021
https://doi.org/10.1007/s00453-021-00823-w
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents