research-article

Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

Author:

Sergio CabelloAuthors Info & Claims

SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

Pages 2143 - 2152

Published: 16 January 2017 Publication History

Abstract

We show how to compute in O(n^11/6 polylog(n)) expected time the diameter and the sum of the pairwise distances in an undirected planar graph with n vertices and positive edge weights. These are the first algorithms for these problems using time O(n^c) for some constant c < 2.

References

[1]

A. Abboud, V. Vassilevska Williams, and J. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 377--391. SIAM, 2016.

Digital Library

[2]

C. Bohler, R. Klein, and C. Liu. Forest-like abstract voronoi diagrams in linear time. In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada, 2014, 2014.

[3]

G. Borradaile, P. Sankowski, and C. Wulff-Nilsen. Min st-cut oracle for planar graphs with near-linear preprocessing time. ACM Transactions on Algorithms, 11(3):16:1--16:29, 2015.

Digital Library

[4]

S. Cabello. Many distances in planar graphs. Algorithmica, 62(1--2):361--381, 2012.

Digital Library

[5]

S. Cabello, E. W. Chambers, and J. Erickson. Multiple-source shortest paths in embedded graphs. SIAM J. Comput., 42(4):1542--1571, 2013.

[6]

S. Cabello and C. Knauer. Algorithms for graphs of bounded treewidth via orthogonal range searching. Comput. Geom., 42(9):815--824, 2009.

Digital Library

[7]

É. Colin de Verdière. Shortest cut graph of a surface with prescribed vertex set. In Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6--8, 2010. Proceedings, Part II, volume 6347 of Lecture Notes in Computer Science, pages 100--111. Springer, 2010.

Digital Library

[8]

J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci., 72(5):868--889, 2006.

Digital Library

[9]

G. N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16:1004--1022, 1987.

Digital Library

[10]

G. N. Frederickson. Planar graph decomposition and all pairs shortest paths. J. ACM, 38(1):162--204, 1991.

Digital Library

[11]

O. Goldreich and D. Ron. Approximating average parameters of graphs. Random Struct. Algorithms, 32(4):473--493, 2008.

Digital Library

[12]

M. T. Goodrich. Planar separators and parallel polygon triangulation. J. Comput. Syst. Sci., 51(3):374--389, 1995.

Digital Library

[13]

P. Indyk. Sublinear time algorithms for metric space problems. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 428--434. ACM, 1999.

Digital Library

[14]

K. Kawarabayashi, P. N. Klein, and C. Sommer. Linearspace approximate distance oracles for planar, boundedgenus and minor-free graphs. In 38th International Colloquium on Automata, Languages and Programming (ICALP), pages 135--146, 2011.

Digital Library

[15]

P. N. Klein. Multiple-source shortest paths in planar graphs. In SODA '05: Proc. 16th Symp. Discrete algorithms, pages 146--155, 2005.

Digital Library

[16]

P. N. Klein, S. Mozes, and C. Sommer. Structured recursive separator decompositions for planar graphs in linear time. In Symposium on Theory of Computing Conference, STOC'13, pages 505--514, 2013. See http://arxiv.org/abs/1208.2223 for the full version.

Digital Library

[17]

P. N. Klein and S. Subramanian. A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica, 22(3):235--249, 1998.

[18]

R. Klein. Concrete and Abstract Voronoi Diagrams, volume 400 of Lecture Notes in Computer Science. Springer, 1989.

[19]

R. Klein. Abstract voronoi diagrams. In M.-Y. Kao, editor, Encyclopedia of Algorithms, pages 1--5. Springer Berlin Heidelberg, 2014.

[20]

R. Klein, E. Langetepe, and Z. Nilforoushan. Abstract voronoi diagrams revisited. Comput. Geom., 42(9):885--902, 2009.

Digital Library

[21]

R. Klein, K. Mehlhorn, and S. Meiser. Randomized incremental construction of abstract voronoi diagrams. Comput. Geom., 3:157--184, 1993.

Digital Library

[22]

D. Marx and M. Pilipczuk. Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. CoRR, abs/1504.05476, 2015.

[23]

S. Mozes, Y. Nussbaum, and O. Weimann. Faster shortest paths in dense distance graphs, with applications. CoRR, abs/1404.0977, 2014.

[24]

S. Mozes and C. Sommer. Exact distance oracles for planar graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pages 209--222. SIAM, 2012.

Digital Library

[25]

G. F. I. Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC, pages 313--322, 2011.

Digital Library

[26]

J. K. Park and C. A. Phillips. Finding minimumquotient cuts in planar graphs. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC '93, pages 766--775, 1993.

Digital Library

[27]

V. Patel. Determining edge expansion and other connectivity measures of graphs of bounded genus. SIAM J. Comput., 42(3):1113--1131, 2013.

[28]

L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Symposium on Theory of Computing Conference, STOC'13, pages 515--524. ACM, 2013.

Digital Library

[29]

M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993--1024, 2004.

Digital Library

[30]

O. Weimann and R. Yuster. Approximating the diameter of planar graphs in near linear time. ACM Transactions on Algorithms, 12(1):12, 2016. Preliminary version in SODA 2012.

Digital Library

[31]

C. Wulff-Nilsen. Wiener index, diameter, and stretch factor of a weighted planar graph in subquadratic time. Technical Report 08--16, Department of Computer Science, University of Copenhagen, 2008. Preliminary version in EurCG 2009.

[32]

C. Wulff-Nilsen. Wiener index, diameter, and stretch factor of a weighted planar digraph in subquadratic time, 2010. Paper M in the PhD thesis of C. Wulff-Nilsen, availalbe at http://www.diku.dk/forskning/phd-studiet/phd/ThesisChristian.pdf.

Cited By

Abboud ACohen-Addad VKlein PMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)New hardness results for planar graph problems in p and an algorithm for sparsest cutProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384310(996-1009)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384310
Li JParter MCharikar MCohen E(2019)Planar diameter via metric compressionProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316358(152-163)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316358
Charalampopoulos PGawrychowski PMozes SWeimann OCharikar MCohen E(2019)Almost optimal distance oracles for planar graphsProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316316(138-151)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316316
Show More Cited By

Recommendations

Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
Special Issue on Soda'17 and Regular Papers

In this article, we show how to compute for n-vertex planar graphs in O(n^11/6 polylog(n)) expected time the diameter and the sum of the pairwise distances. The algorithms work for directed graphs with real weights and no negative cycles. In O(n^15/8 ...
Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. ...
Domination in planar graphs with small diameter

MacGillivray and Seyffarth (J Graph Theory 22 (1996), 213–229) proved that planar graphs of diameter two have domination number at most three and planar graphs of diameter three have domination number at most ten. They also give examples of planar ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

January 2017

2756 pages

Program Chair:
Philip N. Klein
Brown University

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 16 January 2017

Check for updates

Badges

Best Paper

Qualifiers

Research-article

Conference

SODA '17

Sponsor:

SIGACT

SODA '17: Symposium on Discrete Algorithms

January 16 - 19, 2017

Barcelona, Spain

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
99
Total Downloads

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

Reflects downloads up to 09 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abboud ACohen-Addad VKlein PMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)New hardness results for planar graph problems in p and an algorithm for sparsest cutProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384310(996-1009)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384310
Li JParter MCharikar MCohen E(2019)Planar diameter via metric compressionProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316358(152-163)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316358
Charalampopoulos PGawrychowski PMozes SWeimann OCharikar MCohen E(2019)Almost optimal distance oracles for planar graphsProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316316(138-151)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316316
Chan TSkrepetos D(2019)Faster Approximate Diameter and Distance Oracles in Planar GraphsAlgorithmica10.1007/s00453-019-00570-z81:8(3075-3098)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s00453-019-00570-z
Abboud AGawrychowski PMozes SWeimann OCzumaj A(2018)Near-optimal compression for the planar graph metricProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175305(530-549)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175305
Gawrychowski PMozes SWeimann OWulff-Nilsen CCzumaj A(2018)Better tradeoffs for exact distance oracles in planar graphsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175304(515-529)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175304
Gawrychowski PKaplan HMozes SSharir MWeimann OCzumaj A(2018)Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n5/3) timeProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175303(495-514)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175303
Cabello S(2018)Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar GraphsACM Transactions on Algorithms10.1145/321882115:2(1-38)Online publication date: 7-Dec-2018
https://dl.acm.org/doi/10.1145/3218821

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.

Figures

Tables

Media

View Table of Conten