Abstract. We consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms and data structures for maintaining information about 2-and 3-vertex-connectivity, and 3-and 4-edge-connectivity in a planar graph in O(n 1/2 ) amortized time per insertion, deletion, or connectivity query. All of the data structures handle insertions that keep the graph planar without regard to any particular embedding of the graph. Our algorithms are based on a new type of sparsification combined with several properties of separators in planar graphs. Key words. analysis of algorithms, dynamic data structures, edge connectivity, vertex connectivity, planar graphs AMS subject classifications. 68P05, 68Q20, 68R10 PII. S0097539794269072 1. Introduction. Sparse certificates, small graphs that retain some property of a larger graph, appear often in graph theory, especially in problems of edge and vertex connectivity [2, 13, 31, 35] . The main motivation for studying sparse certificates lies in the fact that they are effective tools for speeding up many graph algorithms. To check whether a graph G has a given property P, one can first compute a sparse certificate C for property P and then run an algorithm for P on the certificate rather than on G itself. This is favorable whenever computing certificates is faster than checking property P. This method has led to improved algorithms for testing k-edgeand k-vertex-connectivity sequentially [16, 31, 35] and in parallel [2] , for finding three independent spanning trees [1], and for reliability in distributed networks [26] . With the sparsification technique [8], sparse certificates additionally became an important tool for speeding up dynamic graph algorithms, in which edges may be inserted into and deleted from a graph while some graph property must be maintained throughout the sequence of modifications.
Eppstein et al. REF give an O(n) time algorithm for testing k-edge-connectivity for k ≤ 4 and k-vertex-connectivity for k ≤ 3.
Separator-Based Sparsification II: Edge and Vertex Connectivity
SIAM J. Comput.
Mathematics Computer Science