About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1993
Conference paper
Separator based sparsification for dynamic planar graph algorithms
Abstract
We describe algorithms and data structures for maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We give a fully dynamic planarity testing algorithm that maintains a graph subject to edge insertions and deletions, and allows queries that test whether the graph is currently planar, or whether a potential new edge would violate planarity, in amortized time O(nl/2) per update or query. We maintain the 2-And 3-vertex-connected components, and the 3-And 4-edge-connected components of a planar graph in O(nl/2) time per insertion, deletion or query. We give fully dynamic algorithms for maintaining the connected components, the 2-edge-connected components, and the minimum spanning forest of a planar graph in time (9(log n) per insertion and 0(log2 n) per deletion, assuming that insertions keep the graph planar. All our algorithms improve previous bounds: The improvements are based upon a new type of sparsification combined wit h several properties of separators in planar graphs.