1996/02/01 by David Eppstein, Zvi Galil, Giuseppe F. Italiano +1 · 5 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Software Testing and Debugging Techniques #Planarity testing #Combinatorics #Embedding #Amortized analysis #Graph #Book embedding #Mathematics #Planar graph #Computer science #Algorithm #Time complexity #Data structure #Discrete mathematics #Line graph #Pathwidth #Artificial intelligence
paper · doi:10.1006/jcss.1996.0002
openalex publication_date 1996/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23
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 that allows queries that test whether the graph is currently planar, or whether a potential new edge would violate planarity, inO(n1/2) amortized time per update or query. We give fully dynamic algorithms for maintaining the connected components, the best swap and the minimum spanning forest of a planar graph inO(log n) worst-case time per insertion andO(log2 n) per deletion. Finally, we give fully dynamic algorithms for maintaining the 2-edge-connected components of a planar graph inO(log n) amortized time per insertion andO(log2 n) per deletion. All of the data structures, except for the one that answers planarity queries, handle only insertions that keep the graph planar. All our algorithms improve previous bounds. The improvements are based upon a new type of sparsification combined with several properties of separators in planar graphs.