Document Open Access Logo

Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings

Authors Jacob Holm , Ivor van der Hoog , Eva Rotenberg

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.40.pdf
  • Filesize: 1.19 MB
  • 18 pages

Document Identifiers

Author Details

Jacob Holm
  • University of Copenhagen, Copenhagen, Denmark
Ivor van der Hoog
  • Technical University of Denmark, Lyngby, Denmark
Eva Rotenberg
  • Technical University of Denmark, Lyngby, Denmark

Funding

Ivor van der Hoog and Eva Rotenberg: Partially supported by Independent Research Fund Denmark grants 2020-2023 (9131- 00044B) "Dynamic Network Analysis".
  • Holm, Jacob: Partially supported by the VILLUM Foundation grant 16582, "BARC".
  • van der Hoog, Ivor: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987.

Cite AsGet BibTex

Jacob Holm, Ivor van der Hoog, and Eva Rotenberg. Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.40

Abstract

We study dynamic planar graphs with n vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We dynamically maintain a combinatorial embedding of such a planar graph, subject to connectivity and 2-vertex-connectivity (biconnectivity) queries between pairs of vertices. Whenever a query pair is connected and not biconnected, we find the first and last cutvertex separating them. Additionally, we allow local changes to the embedding by flipping the embedding of a subgraph that is connected by at most two vertices to the rest of the graph. We support all queries and updates in deterministic, worst-case, O(log² n) time, using an O(n)-sized data structure.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • dynamic graphs
  • planarity
  • connectivity

Metrics

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

Related Versions

References

  1. Anders Aamand, Adam Karczmarz, Jakub Lacki, Nikos Parotsidis, Peter M. R. Rasmussen, and Mikkel Thorup. Optimal decremental connectivity in non-sparse graphs. ArXiV, 2021. Google Scholar
  2. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. Acm Transactions on Algorithms (TALG), 2005. URL: https://doi.org/10.1145/1103963.1103966.
  3. Giuseppe Di Battista and Roberto Tamassia. On-line maintenance of triconnected components with spqr-trees. Algorithmica, 1996. URL: https://doi.org/10.1007/BF01961541.
  4. David Eppstein. Dynamic generators of topologically embedded graphs. In ACM-SIAM Symposium on Discrete algorithms (SODA), 2003. URL: https://doi.org/10.5555/644108.644208.
  5. David Eppstein, Zvi Galil, Giuseppe Italiano, and Thomas Spencer. Separator-based sparsification ii: Edge and vertex connectivity. SIAM Journal on Computing, 1999. URL: https://doi.org/10.1137/S0097539794269072.
  6. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. Journal of the ACM (JACM), 1997. URL: https://doi.org/10.1145/265910.265914.
  7. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification. i. planary testing and minimum spanning trees. Journal of Computer and System Sciences (JCSS), 1996. URL: https://doi.org/10.1006/jcss.1996.0002.
  8. David Eppstein, Giuseppe F Italiano, Roberto Tamassia, Robert Tarjan, Jeffery Westbrook, and Moti Yung. Maintenance of a minimum spanning forest in a dynamic plane graph. Journal of Algorithms, 1992. URL: https://doi.org/10.1016/0196-6774(92)90004-V.
  9. David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery R. Westbrook, and Moti Yung. Maintenance of a minimum spanning forest in a dynamic planar graph. Journal of Algorithms, 1992. Google Scholar
  10. Greg Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing, 1985. Google Scholar
  11. Greg Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM Journal on Computing, 1997. URL: https://doi.org/10.1137/S0097539792226825.
  12. Zvi Galil, Giuseppe F. Italiano, and Neil Sarnak. Fully dynamic planarity testing with applications. Journal of the ACM (JACM), 1999. URL: https://doi.org/10.1145/300515.300517.
  13. Dora Giammarresi and Giuseppe F. Italiano. Decremental 2- and 3-connectivity on planar graphs. Algorithmica, 1996. URL: https://doi.org/10.1007/BF01955676.
  14. Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. In Dániel Marx, editor, ACM-SIAM Symposium on Discrete algorithms (SODA), 2021. URL: https://doi.org/10.1137/1.9781611976465.132.
  15. Jens Gustedt. Efficient union-find for planar graphs and other sparse graph classes. Theoretical Computer Science (TCS), 1998. URL: https://doi.org/10.1016/S0304-3975(97)00291-0.
  16. Monika R. Henzinger and Han La Poutré. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In European Symposium on Algorithms (ESA), 1995. Google Scholar
  17. Monika Rauch Henzinger and Valerie King. Fully dynamic 2-edge connectivity algorithm in polylogarithmic time per operation, 1997. Google Scholar
  18. Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM (JACM), 1999. URL: https://doi.org/10.1145/320211.320215.
  19. Monika Rauch Henzinger and Mikkel Thorup. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Structures and Algorithms, 1997. URL: https://doi.org/10.1002/(SICI)1098-2418(199712)11:4<369::AID-RSA5>3.0.CO;2-X.
  20. John Hershberger, Monika Rauch, and Subhash Suri. Data structures for two-edge connectivity in planar graphs. Theoretical Computer Science (TCS), 1994. URL: https://doi.org/10.1016/0304-3975(94)90156-2.
  21. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM), 2001. URL: https://doi.org/10.1145/502090.502095.
  22. Jacob Holm, Giuseppe Italiano, Adam Karczmarz, Jakub Lacki, and Eva Rotenberg. Decremental SPQR-trees for Planar Graphs. In European Symposium on Algorithms (ESA), 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.46.
  23. Jacob Holm and Eva Rotenberg. Dynamic planar embeddings of dynamic graphs. Theory of Computing Systems (TCS), 2017. URL: https://doi.org/10.1007/s00224-017-9768-7.
  24. Jacob Holm and Eva Rotenberg. Fully-dynamic planarity testing in polylogarithmic time. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, PACM Symposium on Theory of Computing (STOC), 2020. URL: https://doi.org/10.1145/3357713.3384249.
  25. Jacob Holm and Eva Rotenberg. Worst-case polylog incremental SPQR-trees: Embeddings, planarity, and triconnectivity. In Shuchi Chawla, editor, ACM-SIAM Symposium on Discrete algorithms (SODA), 2020. URL: https://doi.org/10.1137/1.9781611975994.146.
  26. Jacob Holm and Eva Rotenberg. Good r-divisions imply optimal amortised decremental biconnectivity. Symposium on Theoretical Aspects of Computer Science (STACS), 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.42.
  27. Jacob Holm, Eva Rotenberg, and Mikkel Thorup. Dynamic bridge-finding in Õ(log² n) amortized time. In ACM-SIAM Symposium on Discrete algorithms (SODA), 2018. URL: https://doi.org/10.1137/1.9781611975031.3.
  28. John E. Hopcroft and Robert Endre Tarjan. Efficient planarity testing. Journal of the ACM (JACM), 1974. URL: https://doi.org/10.1145/321850.321852.
  29. Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie. Fully dynamic connectivity in O(log n(log log n)^2) amortized expected time. In ACM-SIAM Symposium on Discrete algorithms (SODA), 2017. URL: https://doi.org/10.1137/1.9781611974782.32.
  30. Giuseppe F. Italiano, Johannes A. La Poutré, and Monika Rauch. Fully dynamic planarity testing in planar embedded graphs (extended abstract). In Thomas Lengauer, editor, European Symposium on Algorithms (ESA, 1993. URL: https://doi.org/10.1007/3-540-57273-2_57.
  31. Bruce Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013. URL: https://doi.org/10.1137/1.9781611973105.81.
  32. Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. Faster Worst Case Deterministic Dynamic Connectivity. In European Symposium on Algorithms (ESA), 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.53.
  33. Jakub Łacki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in O(nlog logn) time. In European Symposium on Algorithms (ESA), 2011. URL: https://doi.org/10.1007/978-3-642-23719-5_14.
  34. Jakub Łacki and Piotr Sankowski. Optimal decremental connectivity in planar graphs. In Symposium on Theoretical Aspects of Computer Science, (STACS), 2015. URL: https://doi.org/10.4230/LIPIcs.STACS.2015.608.
  35. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In Symposium on Foundations of Computer Science (FOCS), 2017. URL: https://doi.org/10.1109/FOCS.2017.92.
  36. Johannes A. La Poutré. Alpha-algorithms for incremental planarity testing (preliminary version). In Frank Thomson Leighton and Michael T. Goodrich, editors, ACM Symposium on Theory of Computing (STOC), 1994. URL: https://doi.org/10.1145/195058.195439.
  37. Johannes A. La Poutré. Maintenance of 2- and 3-edge-connected components of graphs II. SIAM Journal of Computing, 2000. URL: https://doi.org/10.1137/S0097539793257770.
  38. Johannes A. La Poutré, Jan van Leeuwen, and Mark H. Overmars. Maintenance of 2- and 3-edge- connected components of graphs I. Discrete Mathematics, 1993. URL: https://doi.org/10.1016/0012-365X(93)90376-5.
  39. Johannes A. La Poutré and Jeffery R. Westbrook. Dynamic 2-connectivity with backtracking. SIAM Journal of Computing, 1998. URL: https://doi.org/10.1137/S0097539794272582.
  40. Mihai Pǎtraşcu and Erik D Demaine. Logarithmic lower bounds in the cell-probe model. SIAM Journal on Computing, 2006. URL: https://doi.org/10.1137/S0097539705447256.
  41. Robert Endre Tarjan and Renato Fonseca F Werneck. Self-adjusting top trees. In ACM-SIAM Symposium on Discrete algorithms (SODA), 2005. URL: https://doi.org/10.5555/1070432.1070547.
  42. Mikkel Thorup. Decremental dynamic connectivity. In ACM-SIAM Symposium on Discrete algorithms (SODA), 1997. Google Scholar
  43. Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. In ACM Symposium on Theory of Computing (STOC), 2000. URL: https://doi.org/10.1145/335305.335345.
  44. Christian Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In Encyclopedia of Algorithms. Springer Berlin Heidelberg, 2016. URL: https://doi.org/10.1137/1.9781611973105.126.
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 Imprint Privacy Contact