1999/01/01 by Zvi Galil, Giuseppe F. Italiano, Neil Sarnak · 2 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Planarity testing #Combinatorics #Amortized analysis #Planar graph #Graph #Biconnected graph #Time complexity #Computer science #Book embedding #Mathematics #Upper and lower bounds #Enhanced Data Rates for GSM Evolution #Discrete mathematics #Data structure #1-planar graph #Line graph #Graph power #Artificial intelligence
paper · pdf · doi:10.1145/300515.300517
openalex publication_date 1999/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
This paper introduces compressed certificates for planarity, biconnectivity and triconnectivity in planar graphs, and proves many structural properties of certificates in planar graphs. As an application of our compressed certificates, we develop efficient dynamic planar algorithms. In particular, we consider the following three operations on a planar graph G : (i) insert an edge if the resultant graph remains planar; (ii) delete an edge; and (iii) test whether an edge could be added to the graph without violating planarity. We show how to support each of the above operations in O ( n 2/3 ) time, where n is the number of vertices in the graph. The bound for tests and deletions is worst-case, while the bound for insertions is amortized. This is the first algorithm for this problem with sub-linear running time, and it affirmatively answers a question posed in Epstein et al. [1992]. We use our compressed certificates for biconnectivity and triconnectivity to maintain the biconnected and triconnected components of a dynamic planar graph. The time bounds are the same: O ( n 2/3 ) worst-case time per edge deletion, O ( n 2/3 ) amortized time per edge insertion, and O ( n 2/3 ) amortized time per edge insertion, and O ( n 2/3 )worst-case time to check whether two vertices are either biconnected or triconnected.