, No two S-nodes are neighbors, and no two P-nodes are neighbors. It turns out (see e.g. [12]) that the SPQR-tree for a biconnected graph is unique. The (skeleton graphs associated with) nodes of the SPQR-tree are sometimes
Popular conjectures as a barrier for dynamic planar graph algorithms, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pp.477-486, 2016. ,
Popular conjectures imply strong lower bounds for dynamic problems, 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp.434-443, 2014. ,
Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, pp.1199-1218, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00725839
Testing mutual duality of planar graphs, Int. J. Comput. Geometry Appl, vol.24, issue.4, pp.325-346, 2014. ,
The construction and classification of self-dual spherical polyhedra, Journal of Combinatorial Theory, Series B, vol.54, issue.1, pp.37-63, 1992. ,
Fully dynamic maximal matching in O(log n) update time, XX:26 Decremental SPQR-trees for Planar Graphs, vol.44, pp.88-113, 2015. ,
Representations of planar graphs, SIAM Journal on Discrete Mathematics, vol.6, issue.2, pp.214-229, 1993. ,
Generation of simple quadrangulations of the sphere, Discrete Math, vol.305, issue.1-3, pp.33-54, 2005. ,
Decremental single-source reachability and strongly connected components in O(m ? n ) total update time, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pp.315-324, 2016. ,
A new approach to dynamic all pairs shortest paths, J. ACM, vol.51, issue.6, pp.968-992, 2004. ,
Mantaining dynamic matrices for fully dynamic transitive closure, Algorithmica, vol.51, issue.4, pp.387-427, 2008. ,
On-line maintenance of triconnected components with SPQR-trees, Algorithmica, vol.15, issue.4, pp.302-318, 1996. ,
On-line planarity testing, SIAM J. Comput, vol.25, issue.5, pp.956-997, 1996. ,
Dynamic plane transitive closure, Algorithms-ESA 2007, 15th Annual European Symposium, pp.594-604, 2007. ,
Sparsificationa technique for speeding up dynamic graph algorithms, J. ACM, vol.44, issue.5, pp.669-696, 1997. ,
Separator based sparsification I: Planarity testing and minimum spanning trees, J. Comput. Syst. Sci, vol.52, issue.1, pp.3-27, 1996. ,
Separator-based sparsification II: Edge and vertex connectivity, SIAM J. Comput, vol.28, issue.1, pp.341-381, 1998. ,
Maintenance of a minimum spanning forest in a dynamic plane graph, J. Algorithms, vol.13, issue.1, pp.33-54, 1992. ,
Planar graphs, negative weight edges, shortest paths, and near linear time, J. Comput. Syst. Sci, vol.72, issue.5, pp.868-889, 2006. ,
Decremental 2-and 3-connectivity on planar graphs, Algorithmica, vol.16, issue.3, pp.263-287, 1992. ,
Efficient union-find for planar graphs and other sparse graph classes, Theor. Comput. Sci, vol.203, issue.1, pp.123-141, 1998. ,
URL : https://hal.archives-ouvertes.fr/inria-00549672
A Linear Time Implementation of SPQR-Trees, pp.77-90, 2001. ,
, Graph Theory. Addison-Wesley Series in Mathematics, 1969.
Sampling to provide or to bound: With applications to fully dynamic graph algorithms, Random Struct. Algorithms, vol.11, issue.4, pp.369-379, 1997. ,
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, J. ACM, vol.48, issue.4, pp.723-760, 2001. ,
, , p.27
Contracting a Planar Graph Efficiently, 2017. ,
Dynamic planar embeddings of dynamic graphs. Theory of Computing Systems, 2017. ,
Faster fully-dynamic minimum spanning forest, Algorithms-ESA 2015-23rd Annual European Symposium, pp.742-753, 2015. ,
Dividing a graph into triconnected components, SIAM Journal on Computing, vol.2, issue.3, pp.135-158, 1973. ,
A V log V algorithm for isomorphism of triconnected planar graphs, J. Comput. Syst. Sci, vol.7, issue.3, pp.323-331, 1973. ,
Linear time algorithm for isomorphism of planar graphs (preliminary report), Proceedings of the 6th Annual ACM Symposium on Theory of Computing, pp.172-184, 1974. ,
Decremental single-source reachability in planar digraphs, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.1108-1121, 2017. ,
Improved algorithms for min cut and max flow in undirected planar graphs, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pp.313-322, 2011. ,
Algorithms for drawing planar graphs, 2001. ,
Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp.338-355, 2012. ,
Dynamic graph connectivity in polylogarithmic worst case time, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pp.1131-1142, 2013. ,
Faster worst case deterministic dynamic connectivity, 24th Annual European Symposium on Algorithms, ESA 2016, vol.53, pp.1-53, 2016. ,
Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs, 40th Annual Symposium on Foundations of Computer Science, FOCS '99, pp.81-91, 1999. ,
Multiple-source shortest paths in planar graphs, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp.146-155, 2005. ,
Optimization algorithms for planar graphs, 2017. ,
Structured recursive separator decompositions for planar graphs in linear time, Symposium on Theory of Computing Conference, STOC'13, pp.505-514, 2013. ,
Improved deterministic algorithms for decremental reachability and strongly connected components, ACM Trans. Algorithms, vol.9, issue.3, 2013. ,
The power of dynamic distance oracles: Efficient dynamic algorithms for the Steiner tree, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pp.11-20, 2015. ,
Min-cuts and shortest cycles in planar graphs in O(n log log n) time, Algorithms-ESA 2011-19th Annual European Symposium, pp.155-166, 2011. ,
Optimal decremental connectivity in planar graphs, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, pp.608-621, 2015. ,
Zur allgemeinen kurventheorie, Fund. Math, vol.10, pp.96-115, 1927. ,
Dynamic spanning forest with worstcase update time: adaptive, Las Vegas, and O(n 1/2-)-time, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.1122-1129, 2017. ,
Dynamic minimum spanning forest with subpolynomial worst-case update time, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, 2017. ,
Improved dynamic reachability algorithms for directed graphs, SIAM J. Comput, vol.37, issue.5, pp.1455-1471, 2008. ,
Embedding in the plane with orientation constraints: The angle graph, Annals of the New York Academy of Sciences, vol.555, issue.1, pp.340-346, 1989. ,
URL : https://hal.archives-ouvertes.fr/hal-00261218
Dynamic transitive closure via dynamic matrix inverse (extended abstract), 45th Symposium on Foundations of Computer Science FOCS, pp.509-517, 2004. ,
Fully dynamic maximal matching in constant update time, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pp.325-334, 2016. ,
A fully dynamic data structure for reachability in planar digraphs, Algorithms-ESA '93, First Annual European Symposium, pp.372-383, 1993. ,
Near-optimal fully-dynamic graph connectivity, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp.343-350, 2000. ,
Worst-case update times for fully-dynamic all-pairs shortest paths, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp.112-119, 2005. ,
Faster deterministic fully-dynamic graph connectivity, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pp.1757-1769, 2013. ,
Fully-dynamic minimum spanning forest with improved worst-case update time, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.1130-1143, 2017. ,