Document Open Access Logo

What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs?

Authors Amir Abboud , Shay Mozes , Oren Weimann

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.4.pdf
  • Filesize: 1.09 MB
  • 20 pages

Document Identifiers

Author Details

Amir Abboud
  • Weizmann Institute of Science, Rehovot, Israel
Shay Mozes
  • Reichman University, Herzliya, Israel
Oren Weimann
  • University of Haifa, Haifa, Israel

Funding

  • Abboud, Amir: Supported by an Alon scholarship and a research grant from the Center for New Scientists at the Weizmann Institute of Science.
  • Mozes, Shay: Israel Science Foundation grant 810/21.
  • Weimann, Oren: Israel Science Foundation grant 810/21.

Cite As Get BibTex

Amir Abboud, Shay Mozes, and Oren Weimann. What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs?. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.4

Abstract

The Voronoi diagrams technique, introduced by Cabello [SODA'17] to compute the diameter of planar graphs in subquadratic time, has revolutionized the field of distance computations in planar graphs. We present novel applications of this technique in static, fault-tolerant, and partially-dynamic undirected unweighted planar graphs, as well as some new limitations.  
- In the static case, we give n^{3+o(1)}/D² and Õ(n⋅D²) time algorithms for computing the diameter of a planar graph G with diameter D. These are faster than the state of the art Õ(n^{5/3}) [SODA'18] when D < n^{1/3} or D > n^{2/3}. 
- In the fault-tolerant setting, we give an n^{7/3+o(1)} time algorithm for computing the diameter of G⧵ {e} for every edge e in G (the replacement diameter problem). This should be compared with the naive Õ(n^{8/3}) time algorithm that runs the static algorithm for every edge. 
- In the incremental setting, where we wish to maintain the diameter while adding edges, we present an algorithm with total running time n^{7/3+o(1)}. This should be compared with the naive Õ(n^{8/3}) time algorithm that runs the static algorithm after every update. 
- We give a lower bound (conditioned on the SETH) ruling out an amortized O(n^{1-ε}) update time for maintaining the diameter in weighted planar graph. The lower bound holds even for incremental or decremental updates.  
Our upper bounds are obtained by novel uses and manipulations of Voronoi diagrams. These include maintaining the Voronoi diagram when edges of the graph are deleted, allowing the sites of the Voronoi diagram to lie on a BFS tree level (rather than on boundaries of r-division), and a new reduction from incremental diameter to incremental distance oracles that could be of interest beyond planar graphs. Our lower bound is the first lower bound for a dynamic planar graph problem that is conditioned on the SETH.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Planar graphs
  • diameter
  • dynamic graphs
  • fault tolerance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. ACM Trans. Algorithms, 17(4):30:1-30:40, 2021. URL: https://doi.org/10.1145/3469834.
  2. Amir Abboud, Vincent Cohen-Addad, and Philip N. Klein. New hardness results for planar graph problems in P and an algorithm for sparsest cut. In 52nd STOC, pages 996-1009, 2020. Google Scholar
  3. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In 57th FOCS, pages 477-486, 2016. Google Scholar
  4. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In FOCS, pages 434-443, 2014. Google Scholar
  5. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In SODA, pages 377-391, 2016. Google Scholar
  6. Ittai Abraham, Shiri Chechik, and Cyril Gavoille. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In 44th annual ACM symposium on Theory of computing, pages 1199-1218, 2012. Google Scholar
  7. Raghavendra Addanki, Andrew McGregor, and Cameron Musco. Non-adaptive edge counting and sampling via bipartite independent set queries. arXiv preprint arXiv:2207.02817, 2022. Google Scholar
  8. A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2(1):195-208, 1987. Google Scholar
  9. Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. Algorithms and hardness for diameter in dynamic graphs. In 46th ICALP, volume 132, pages 13:1-13:14, 2019. Google Scholar
  10. Srinivasa Rao Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel H. M. Smid, and Christos D. Zaroliagis. Planar spanners and approximate shortest path queries among obstacles in the plane. In 4th ESA, volume 1136, pages 514-528, 1996. Google Scholar
  11. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Toward tight approximation bounds for graph diameter and eccentricities. SIAM J. Comput., 50(4):1155-1199, 2021. URL: https://doi.org/10.1137/18M1226737.
  12. Surender Baswana, Utkarsh Lath, and Anuradha S. Mehta. Single source distance oracle for planar digraphs avoiding a failed node or link. In 23rd SODA, pages 223-232, 2012. Google Scholar
  13. Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge estimation with independent set oracles. ACM Transactions on Algorithms (TALG), 16(4):1-27, 2020. Google Scholar
  14. Boaz Ben-Moshe, Binay K. Bhattacharya, Qiaosheng Shi, and Arie Tamir. Efficient algorithms for center problems in cactus networks. Theor. Comput. Sci., 378(3):237-252, 2007. Google Scholar
  15. P. Berman and S.P Kasiviswanathan. Faster approximation of distances in graphs. In Proc. of the 10th International Workshop on Algorithms and Data Structures (WADS), pages 541-552, 2007. Google Scholar
  16. Anup Bhattachrya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Faster counting and sampling algorithms using colorful decision oracle. Leibniz International Proceedings in Informatics (LIPIcs), 219, 2022. Google Scholar
  17. Édouard Bonnet. 4 vs 7 sparse undirected unweighted diameter is SETH-hard at time n^4/3. ACM Trans. Algorithms, 18(2):11:1-11:14, 2022. URL: https://doi.org/10.1145/3494540.
  18. Glencora Borradaile, Seth Pettie, and Christian Wulff-Nilsen. Connectivity oracles for planar graphs. In 13th SWAT, volume 7357, pages 316-327, 2012. Google Scholar
  19. Glencora Borradaile, Piotr Sankowski, and Christian Wulff-Nilsen. Min st-cut oracle for planar graphs with near-linear preprocessing time. In 51th FOCS, pages 601-610, 2010. Google Scholar
  20. Costas Busch, Ryan LaFortune, and Srikanta Tirthapura. Sparse covers for planar graphs and graphs that exclude a fixed minor. Algorithmica, 69(3):658-684, 2014. URL: https://doi.org/10.1007/s00453-013-9757-4.
  21. Sergio Cabello. Many distances in planar graphs. Algorithmica, 62(1-2):361-381, 2012. URL: https://doi.org/10.1007/s00453-010-9459-0.
  22. Sergio Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. In 28'th SODA, pages 2143-2152, 2017. Google Scholar
  23. Timothy M. Chan. All-pairs shortest paths for unweighted undirected graphs in o(mn) time. ACM Trans. Algorithms, 8(4):34:1-34:17, 2012. Google Scholar
  24. Timothy M. Chan and Dimitrios Skrepetos. Faster approximate diameter and distance oracles in planar graphs. Algorithmica, 81(8):3075-3098, 2019. URL: https://doi.org/10.1007/s00453-019-00570-z.
  25. Hsien-Chih Chang, Robert Krauthgamer, and Zihan Tan. Almost-linear ε-emulators for planar graphs. In 54th STOC, pages 1311-1324, 2022. Google Scholar
  26. Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Almost optimal distance oracles for planar graphs. In 51st STOC, pages 138-151, 2019. Google Scholar
  27. Panagiotis Charalampopoulos and Adam Karczmarz. Single-source shortest paths and strong connectivity in dynamic planar graphs. J. Comput. Syst. Sci., 124:97-111, 2022. URL: https://doi.org/10.1016/j.jcss.2021.09.008.
  28. Panagiotis Charalampopoulos, Shay Mozes, and Benjamin Tebeka. Exact distance oracles for planar graphs with failing vertices. In 30th SODA, pages 2110-2123, 2019. Google Scholar
  29. Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams. Better approximation algorithms for the graph diameter. In 25th SODA, pages 1041-1052, 2014. Google Scholar
  30. Danny Z. Chen and Jinhui Xu. Shortest path queries in planar graphs. In 32nd STOC, pages 469-478, 2000. Google Scholar
  31. Victor Chepoi and Feodor F. Dragan. A linear-time algorithm for finding a central vertex of a chordal graph. In ESA, pages 159-170, 1994. Google Scholar
  32. Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Michel Habib, and Yann Vaxès. Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs. In SoCG, pages 59-68, 2008. Google Scholar
  33. Victor Chepoi, Feodor F. Dragan, and Yann Vaxès. Center and diameter problems in plane triangulations and quadrangulations. In SODA, pages 346-355, 2002. Google Scholar
  34. K.L. Clarkson and P.W. Shor. Applications of random sampling in computational geometry, ii. Discrete & Computational Geometry, 4(5):387-421, 1989. Google Scholar
  35. Vincent Cohen-Addad, Søren Dahlgaard, and Christian Wulff-Nilsen. Fast and compact exact distance oracle for planar graphs. In 58th FOCS, pages 962-973, 2017. Google Scholar
  36. Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. Hardness of approximate diameter: Now for undirected graphs. In 62nd FOCS, pages 1021-1032, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00102.
  37. Debarati Das, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. A near-optimal offline algorithm for dynamic all-pairs shortest paths in planar digraphs. In 33rd SODA, pages 3482-3495, 2022. Google Scholar
  38. Holger Dell, John Lapinskas, and Kitty Meeks. Approximately counting and sampling small witnesses using a colorful decision oracle. SIAM J. Comput., 51(4):849-899, 2022. URL: https://doi.org/10.1137/19m130604x.
  39. Hristo Djidjev. Efficient algorithms for shortest path queries in planar digraphs. In 22nd WG, volume 1197, pages 151-165, 1996. Google Scholar
  40. Feodor F. Dragan and Falk Nicolai. Lexbfs-orderings of distance-hereditary graphs with application to the diametral pair problem. Discrete Applied Mathematics, 98(3):191-207, 2000. Google Scholar
  41. D. Eppstein. Subgraph isomorphism in planar graphs and related problems. In 6th SODA, pages 632-640, 1995. Google Scholar
  42. 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. Google Scholar
  43. Arthur M. Farley and Andrzej Proskurowski. Computation of the center and diameter of outerplanar graphs. Discrete Applied Mathematics, 2(3):185-191, 1980. Google Scholar
  44. G. N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16(6):1004-1022, 1987. Google Scholar
  45. Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann. Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n^5/3) time. SIAM J. Comput., 50(2):509-554, 2021. Google Scholar
  46. Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Planar negative k-cycle. In 32nd SODA, pages 2717-2724, 2021. Google Scholar
  47. Pawel Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen. Better tradeoffs for exact distance oracles in planar graphs. In SODA, 2018. Google Scholar
  48. Qian-Ping Gu and Gengchun Xu. Constant query time (1+ε)-approximate distance oracle for planar graphs. Theor. Comput. Sci., 761:78-88, 2019. Google Scholar
  49. John Hershberger and Subhash Suri. Matrix searching with the shortest-path metric. SIAM J. Comput., 26(6):1612-1634, 1997. Google Scholar
  50. Thore Husfeldt. Computing graph distances parameterized by treewidth and diameter. In IPEC, pages 16:1-16:11, 2016. Google Scholar
  51. Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, and Piotr Sankowski. Decremental single-source reachability in planar digraphs. In 49th STOC, pages 1108-1121, 2017. Google Scholar
  52. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In 43rd STOC, pages 313-322, 2011. Google Scholar
  53. Adam Karczmarz. Decrementai transitive closure and shortest paths for planar digraphs and beyond. In 29th SODA, pages 73-92, 2018. Google Scholar
  54. Ken-ichi Kawarabayashi, Philip N. Klein, and Christian Sommer. Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In 38th ICALP, volume 6755, pages 135-146, 2011. Google Scholar
  55. Ken-ichi Kawarabayashi, Christian Sommer, and Mikkel Thorup. More compact oracles for approximate distances in undirected planar graphs. In 24th SODA, pages 550-563, 2013. Google Scholar
  56. P. N. Klein. Multiple-source shortest paths in planar graphs. In 16th SODA, pages 146-155, 2005. Google Scholar
  57. P. N. Klein, S. Mozes, and C. Sommer. Structured recursive separator decompositions for planar graphs in linear time. In 45th STOC, pages 505-514, 2013. Google Scholar
  58. Philip N. Klein. Preprocessing an undirected planar network to enable fast approximate distance queries. In 13th SODA, pages 820-827, 2002. Google Scholar
  59. Jakub Lacki and Piotr Sankowski. Optimal decremental connectivity in planar graphs. Theory Comput. Syst., 61(4):1037-1053, 2017. Google Scholar
  60. Hung Le and Christian Wulff-Nilsen. Optimal approximate distance oracle for planar graphs. In 62nd FOCS, pages 363-374, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00044.
  61. R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math, 36(2):177-189, 1979. Google Scholar
  62. J. Łącki and P. Sankowski. Min-cuts and shortest cycles in planar graphs in O(n log log n) time. In 19th ESA, pages 155-166, 2011. Google Scholar
  63. Yaowei Long and Seth Pettie. Planar distance oracles with better time-space tradeoffs. In 32nd SODA, pages 2517-2536, 2021. Google Scholar
  64. Shay Mozes and Christian Sommer. Exact distance oracles for planar graphs. In 23rd SODA, pages 209-222, 2012. Google Scholar
  65. Yahav Nussbaum. Improved distance queries in planar graphs. In 12th WADS, pages 642-653, 2011. Google Scholar
  66. Stephan Olariu. A simple linear-time algorithm for computing the center of an interval graph. International Journal of Computer Mathematics, 34:121-128, 1990. Google Scholar
  67. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In 45th STOC, pages 515-524, 2013. Google Scholar
  68. Sairam Subramanian. A fully dynamic data structure for reachability in planar digraphs. In 1st ESA, volume 726, pages 372-383, 1993. Google Scholar
  69. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. Google Scholar
  70. O. Weimann and R. Yuster. Approximating the diameter of planar graphs in near linear time. ACM Trans. Algorithms, 12(1):12:1-12:13, 2016. Google Scholar
  71. Ryan Williams. A new algorithm for optimal constraint satisfaction and its implications. In 31st ICALP, pages 1227-1237, 2004. Google Scholar
  72. C. Wulff-Nilsen. Wiener index and diameter of a planar graph in subquadratic time. Technical report, 08-16, Department of Computer Science, University of Copenhagen, 2008. Available at http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/08-16.pdf. Preliminary version in EurCG 2009.
  73. Christian Wulff-Nilsen. Algorithms for planar graphs and graphs in metric spaces. PhD thesis, University of Copenhagen, 2010. Google Scholar
  74. Christian Wulff-Nilsen. Approximate distance oracles for planar graphs with improved query time-space tradeoff. In 27th SODA, pages 351-362, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact