Document Open Access Logo

Decremental SPQR-trees for Planar Graphs

Authors Jacob Holm , Giuseppe F. Italiano , Adam Karczmarz , Jakub Lacki , Eva Rotenberg

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2018.46.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Data structures design and analysis
Keywords
  • Graph embeddings
  • data structures
  • graph algorithms
  • planar graphs
  • SPQR-trees
  • triconnectivity

Metrics

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

Abstract

We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over Omega(n) operations, is O(log^2 n). Via SPQR-trees, we give a decremental data structure for maintaining 3-vertex connectivity in planar graphs. It answers queries in O(1) time and processes edge deletions and contractions in O(log^2 n) amortized time. The previous best supported deletions and insertions in O(sqrt{n}) time.

Cite As Get BibTex

Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, and Eva Rotenberg. Decremental SPQR-trees for Planar Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.46

Author Details

Jacob Holm
  • University of Copenhagen, Denmark
Giuseppe F. Italiano
  • University of Rome Tor Vergata, Italy
Adam Karczmarz
  • University of Warsaw, Poland
Jakub Lacki
  • Google Research, USA
Eva Rotenberg
  • Technical University of Denmark, Denmark

Funding

  • Holm, Jacob: Jacob Holm is supported by Mikkel Thorup’s Advanced Grant DFF-0602-02499B from the Danish Council for Independent Research under the Sapere Aude research career programme.
  • Italiano, Giuseppe F.: Giuseppe F. Italiano is partially supported by the Italian Ministry of Education, University and Research under Project AMANDA (Algorithmics for MAssive and Networked DAta).
  • Karczmarz, Adam: Adam Karczmarz is supported by the grants 2014/13/B/ST6/01811 and 2017/24/T/ST6/00036 of the Polish National Science Center.
  • Lacki, Jakub: When working on this paper Jakub Łącki was partly supported by the EU FET project MULTIPLEX no. 317532 and the Google Focused Award on "Algorithms for Large-scale Data Analysis" and Polish National Science Center grant number 2014/13/B/ST6/01811. Part of this work was done while Jakub Łącki was visiting the Simons Institute for the Theory of Computing.

References

  1. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 477-486, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.58.
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434-443, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.53.
  3. Ittai Abraham, Shiri Chechik, and Cyril Gavoille. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 1199-1218, 2012. URL: http://dx.doi.org/10.1145/2213977.2214084.
  4. Patrizio Angelini, Thomas Bläsius, and Ignaz Rutter. Testing mutual duality of planar graphs. Int. J. Comput. Geometry Appl., 24(4):325-346, 2014. URL: http://dx.doi.org/10.1142/S0218195914600103.
  5. Dan Archdeacon and R Bruce Richter. The construction and classification of self-dual spherical polyhedra. J. Comb. Theory, Series B, 54(1):37-63, 1992. URL: http://dx.doi.org/10.1016/0095-8956(92)90065-6.
  6. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O(log n) update time. SIAM J. Comput., 44(1):88-113, 2015. URL: http://dx.doi.org/10.1137/130914140.
  7. Graham R. Brightwell and Edward R. Scheinerman. Representations of planar graphs. SIAM J. Discrete Math., 6(2):214-229, 1993. URL: http://dx.doi.org/10.1137/0406017.
  8. Gunnar Brinkmann, Sam Greenberg, Catherine Greenhill, Brendan D. Mckay, Robin Thomas, and Paul Wollan. Generation of simple quadrangulations of the sphere. Discrete Math., 305(1-3):33-54, 2005. URL: http://dx.doi.org/10.1016/j.disc.2005.10.005.
  9. Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, and Nikos Parotsidis. Decremental single-source reachability and strongly connected components in Õ(m√n) total update time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 315-324, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.42.
  10. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM, 51(6):968-992, 2004. URL: http://dx.doi.org/10.1145/1039488.1039492.
  11. Camil Demetrescu and Giuseppe F. Italiano. Mantaining dynamic matrices for fully dynamic transitive closure. Algorithmica, 51(4):387-427, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9051-4.
  12. Giuseppe Di Battista and Roberto Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algorithmica, 15(4):302-318, 1996. URL: http://dx.doi.org/10.1007/BF01961541.
  13. Giuseppe Di Battista and Roberto Tamassia. On-line planarity testing. SIAM J. Comput., 25(5):956-997, 1996. URL: http://dx.doi.org/10.1137/S0097539794280736.
  14. Krzysztof Diks and Piotr Sankowski. Dynamic plane transitive closure. In Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, pages 594-604, 2007. URL: http://dx.doi.org/10.1007/978-3-540-75520-3_53.
  15. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669-696, 1997. URL: http://dx.doi.org/10.1145/265910.265914.
  16. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification I: Planarity testing and minimum spanning trees. J. Comput. Syst. Sci., 52(1):3-27, 1996. URL: http://dx.doi.org/10.1006/jcss.1996.0002.
  17. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator-based sparsification II: Edge and vertex connectivity. SIAM J. Comput., 28(1):341-381, 1998. Announced at STOC '93. URL: http://dx.doi.org/10.1137/S0097539794269072.
  18. David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert Endre Tarjan, Jeffery Westbrook, and Moti Yung. Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algorithms, 13(1):33-54, 1992. URL: http://dx.doi.org/10.1016/0196-6774(92)90004-V.
  19. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci., 72(5):868-889, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2005.05.007.
  20. Dora Giammarresi and Giuseppe F. Italiano. Decremental 2- and 3-connectivity on planar graphs. Algorithmica, 16(3):263-287, 1996. Announced at SWAT 1992. URL: http://dx.doi.org/10.1007/BF01955676.
  21. Jens Gustedt. Efficient union-find for planar graphs and other sparse graph classes. Theor. Comput. Sci., 203(1):123-141, 1998. URL: http://dx.doi.org/10.1016/S0304-3975(97)00291-0.
  22. Carsten Gutwenger and Petra Mutzel. A Linear Time Implementation of SPQR-Trees, pages 77-90. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001. URL: http://dx.doi.org/10.1007/3-540-44541-2_8.
  23. Frank Harary. Graph Theory. Addison-Wesley Series in Mathematics. Addison Wesley, 1969. Google Scholar
  24. Monika Rauch Henzinger and Mikkel Thorup. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Struct. Algorithms, 11(4):369-379, 1997. URL: http://dx.doi.org/10.1002/(SICI)1098-2418(199712)11:4<369::AID-RSA5>3.0.CO;2-X.
  25. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. URL: http://dx.doi.org/10.1145/502090.502095.
  26. Jacob Holm, Giuseppe F Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, and Piotr Sankowski. Contracting a planar graph efficiently. In LIPIcs-Leibniz International Proceedings in Informatics, volume 87. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  27. Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Eva Rotenberg. Decremental SPQR-trees for Planar Graphs. ArXiv e-prints, 2018. URL: http://arxiv.org/abs/1806.10772.
  28. Jacob Holm and Eva Rotenberg. Dynamic planar embeddings of dynamic graphs. Theory of Computing Systems, Apr 2017. URL: http://dx.doi.org/10.1007/s00224-017-9768-7.
  29. Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum spanning forest. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, Sept. 14-16, 2015, Proceedings, pages 742-753, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_62.
  30. John E. Hopcroft and Robert Endre Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2(3):135-158, 1973. URL: http://dx.doi.org/10.1137/0202012.
  31. John E. Hopcroft and Robert Endre Tarjan. A V log V algorithm for isomorphism of triconnected planar graphs. J. Comput. Syst. Sci., 7(3):323-331, 1973. URL: http://dx.doi.org/10.1016/S0022-0000(73)80013-3.
  32. John E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1974, Seattle, Washington, USA, pages 172-184, 1974. URL: http://dx.doi.org/10.1145/800119.803896.
  33. Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski. Decremental single-source reachability in planar digraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1108-1121, 2017. URL: http://dx.doi.org/10.1145/3055399.3055480.
  34. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian 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 2011, San Jose, CA, USA, 6-8 June 2011, pages 313-322, 2011. URL: http://dx.doi.org/10.1145/1993636.1993679.
  35. Goossen Kant. Algorithms for drawing planar graphs, 2001. Google Scholar
  36. Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir. Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 338-355, 2012. URL: http://portal.acm.org/citation.cfm?id=2095147&CFID=63838676&CFTOKEN=79617016.
  37. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1131-1142, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.81.
  38. Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. Faster worst case deterministic dynamic connectivity. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 53:1-53:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.53.
  39. Valerie King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 81-91, 1999. URL: http://dx.doi.org/10.1109/SFFCS.1999.814580.
  40. Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, BC, Canada, January 23-25, 2005, pages 146-155, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  41. Philip N. Klein and Shay Mozes. Optimization algorithms for planar graphs, 2017. URL: http://planarity.org.
  42. Jakub Łącki. Improved deterministic algorithms for decremental reachability and strongly connected components. ACM Trans. Algorithms, 9(3):27:1-27:15, 2013. URL: http://dx.doi.org/10.1145/2483699.2483707.
  43. Jakub Łącki, Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski, and Anna Zych. The power of dynamic distance oracles: Efficient dynamic algorithms for the Steiner tree. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 11-20, 2015. URL: http://dx.doi.org/10.1145/2746539.2746615.
  44. Jakub Łącki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in O(nlog logn) time. In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, pages 155-166, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_14.
  45. Jakub Łącki and Piotr Sankowski. Optimal decremental connectivity in planar graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 608-621, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.608.
  46. Karl Menger. Zur allgemeinen kurventheorie. Fund. Math., 10:96-115, 1927. Google Scholar
  47. Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n^1/2 - ε)-time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1122-1129, 2017. URL: http://dx.doi.org/10.1145/3055399.3055447.
  48. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science, FOCS 2017, 2017. To appear. Google Scholar
  49. Liam Roditty and Uri Zwick. Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput., 37(5):1455-1471, 2008. URL: http://dx.doi.org/10.1137/060650271.
  50. Pierre Rosenstiehl. Embedding in the plane with orientation constraints: The angle graph. Annals of the New York Academy of Sciences, 555(1):340-346, 1989. URL: http://dx.doi.org/10.1111/j.1749-6632.1989.tb22470.x.
  51. Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse (extended abstract). In 45th Symposium on Foundations of Computer Science FOCS 2004, 17-19 October 2004, Rome, Italy, Proceedings, pages 509-517, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.25.
  52. Shay Solomon. Fully dynamic maximal matching in constant update time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 325-334, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.43.
  53. Sairam Subramanian. A fully dynamic data structure for reachability in planar digraphs. In Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30 - October 2, 1993, Proceedings, pages 372-383, 1993. URL: http://dx.doi.org/10.1007/3-540-57273-2_72.
  54. Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 343-350, 2000. URL: http://dx.doi.org/10.1145/335305.335345.
  55. Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 112-119, 2005. URL: http://dx.doi.org/10.1145/1060590.1060607.
  56. Christian Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1757-1769, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.126.
  57. Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1130-1143, 2017. URL: http://dx.doi.org/10.1145/3055399.3055415.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »