1998/01/01 by David Eppstein, Zvi Galil, Giuseppe F. Italiano +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Combinatorics #Planar graph #Planar straight-line graph #Planarity testing #Embedding #Book embedding #Graph embedding #Vertex (graph theory) #Graph #Mathematics #Computer science #Discrete mathematics #Line graph #Pathwidth #Artificial intelligence
paper · doi:10.1137/s0097539794269072
openalex publication_date 1998/01/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/06/11
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(n1/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.