, 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

A. Abboud and S. Dahlgaard, Popular conjectures as a barrier for dynamic planar graph algorithms, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pp.477-486, 2016.

A. Abboud and V. Williams, Popular conjectures imply strong lower bounds for dynamic problems, 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp.434-443, 2014.

I. Abraham, S. Chechik, and C. Gavoille, 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

P. Angelini, T. Bläsius, and I. Rutter, Testing mutual duality of planar graphs, Int. J. Comput. Geometry Appl, vol.24, issue.4, pp.325-346, 2014.

D. Archdeacon and B. Richter, The construction and classification of self-dual spherical polyhedra, Journal of Combinatorial Theory, Series B, vol.54, issue.1, pp.37-63, 1992.

S. Baswana, M. Gupta, and S. Sen, Fully dynamic maximal matching in O(log n) update time, XX:26 Decremental SPQR-trees for Planar Graphs, vol.44, pp.88-113, 2015.

R. Graham, E. R. Brightwell, and . Scheinerman, Representations of planar graphs, SIAM Journal on Discrete Mathematics, vol.6, issue.2, pp.214-229, 1993.

G. Brinkmann, S. Greenberg, C. Greenhill, B. D. Mckay, R. Thomas et al., Generation of simple quadrangulations of the sphere, Discrete Math, vol.305, issue.1-3, pp.33-54, 2005.

S. Chechik, T. D. Hansen, G. F. Italiano, J. ?¸acki?¸acki, and N. Parotsidis, 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.

C. Demetrescu and G. F. Italiano, A new approach to dynamic all pairs shortest paths, J. ACM, vol.51, issue.6, pp.968-992, 2004.

C. Demetrescu and G. F. Italiano, Mantaining dynamic matrices for fully dynamic transitive closure, Algorithmica, vol.51, issue.4, pp.387-427, 2008.

G. D. Battista and R. Tamassia, On-line maintenance of triconnected components with SPQR-trees, Algorithmica, vol.15, issue.4, pp.302-318, 1996.

G. D. Battista and R. Tamassia, On-line planarity testing, SIAM J. Comput, vol.25, issue.5, pp.956-997, 1996.

K. Diks and P. Sankowski, Dynamic plane transitive closure, Algorithms-ESA 2007, 15th Annual European Symposium, pp.594-604, 2007.

D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig, Sparsificationa technique for speeding up dynamic graph algorithms, J. ACM, vol.44, issue.5, pp.669-696, 1997.

D. Eppstein, Z. Galil, G. F. Italiano, and T. H. Spencer, Separator based sparsification I: Planarity testing and minimum spanning trees, J. Comput. Syst. Sci, vol.52, issue.1, pp.3-27, 1996.

D. Eppstein, Z. Galil, G. F. Italiano, and T. H. Spencer, Separator-based sparsification II: Edge and vertex connectivity, SIAM J. Comput, vol.28, issue.1, pp.341-381, 1998.

D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook et al., Maintenance of a minimum spanning forest in a dynamic plane graph, J. Algorithms, vol.13, issue.1, pp.33-54, 1992.

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

D. Giammarresi and G. F. Italiano, Decremental 2-and 3-connectivity on planar graphs, Algorithmica, vol.16, issue.3, pp.263-287, 1992.

J. Gustedt, 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

C. Gutwenger and P. Mutzel, A Linear Time Implementation of SPQR-Trees, pp.77-90, 2001.

F. Harary, Graph Theory. Addison-Wesley Series in Mathematics, 1969.

M. Rauch-henzinger and M. Thorup, Sampling to provide or to bound: With applications to fully dynamic graph algorithms, Random Struct. Algorithms, vol.11, issue.4, pp.369-379, 1997.

J. Holm, K. De-lichtenberg, and M. Thorup, 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.

J. Holm, G. F. Italiano, A. Karczmarz, J. ??cki, E. Rotenberg et al., , p.27

J. Holm, G. F. Italiano, A. Karczmarz, J. ?¸acki?¸acki, E. Rotenberg et al., Contracting a Planar Graph Efficiently, 2017.

J. Holm and E. Rotenberg, Dynamic planar embeddings of dynamic graphs. Theory of Computing Systems, 2017.

J. Holm, E. Rotenberg, and C. Wulff-nilsen, Faster fully-dynamic minimum spanning forest, Algorithms-ESA 2015-23rd Annual European Symposium, pp.742-753, 2015.

J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM Journal on Computing, vol.2, issue.3, pp.135-158, 1973.

J. E. Hopcroft and R. E. Tarjan, A V log V algorithm for isomorphism of triconnected planar graphs, J. Comput. Syst. Sci, vol.7, issue.3, pp.323-331, 1973.

J. E. Hopcroft and J. K. Wong, 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.

G. F. Italiano, A. Karczmarz, J. ?¸acki?¸acki, and P. Sankowski, Decremental single-source reachability in planar digraphs, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.1108-1121, 2017.

G. F. Italiano, Y. Nussbaum, P. Sankowski, and C. Wulff-nilsen, 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.

G. Kant, Algorithms for drawing planar graphs, 2001.

H. Kaplan, S. Mozes, Y. Nussbaum, and M. Sharir, 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.

M. Bruce, V. Kapron, B. King, and . Mountjoy, 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.

C. Kejlberg-rasmussen, T. Kopelowitz, S. Pettie, and M. Thorup, Faster worst case deterministic dynamic connectivity, 24th Annual European Symposium on Algorithms, ESA 2016, vol.53, pp.1-53, 2016.

V. King, 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.

P. N. Klein, Multiple-source shortest paths in planar graphs, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp.146-155, 2005.

N. Philip, S. Klein, and . Mozes, Optimization algorithms for planar graphs, 2017.

P. N. Klein, S. Mozes, and C. Sommer, Structured recursive separator decompositions for planar graphs in linear time, Symposium on Theory of Computing Conference, STOC'13, pp.505-514, 2013.

J. ?¸acki?¸acki, Improved deterministic algorithms for decremental reachability and strongly connected components, ACM Trans. Algorithms, vol.9, issue.3, 2013.

J. ?¸acki?¸acki, J. O?wieja, M. Pilipczuk, P. Sankowski, and A. Zych, 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.

J. ?¸acki?¸acki and P. Sankowski, 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.

J. ?¸acki?¸acki and P. Sankowski, Optimal decremental connectivity in planar graphs, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, pp.608-621, 2015.

K. Menger, Zur allgemeinen kurventheorie, Fund. Math, vol.10, pp.96-115, 1927.

D. Nanongkai and T. Saranurak, 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.

D. Nanongkai, T. Saranurak, and C. Wulff-nilsen, Dynamic minimum spanning forest with subpolynomial worst-case update time, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, 2017.

L. Roditty and U. Zwick, Improved dynamic reachability algorithms for directed graphs, SIAM J. Comput, vol.37, issue.5, pp.1455-1471, 2008.

P. Rosenstiehl, 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

P. Sankowski, Dynamic transitive closure via dynamic matrix inverse (extended abstract), 45th Symposium on Foundations of Computer Science FOCS, pp.509-517, 2004.

S. Solomon, Fully dynamic maximal matching in constant update time, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pp.325-334, 2016.

S. Subramanian, A fully dynamic data structure for reachability in planar digraphs, Algorithms-ESA '93, First Annual European Symposium, pp.372-383, 1993.

M. Thorup, Near-optimal fully-dynamic graph connectivity, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp.343-350, 2000.

M. Thorup, 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.

C. Wulff-nilsen, Faster deterministic fully-dynamic graph connectivity, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pp.1757-1769, 2013.

C. Wulff-nilsen, 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.