### Fully dynamic planarity testing with applicationsFully dynamic planarity testing with applications

Access Restriction
Subscribed

 Author Galil, Zvi ♦ Italiano, Giuseppe F. ♦ Sarnak, Neil Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1999 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Dynamic graph algorithms ♦ Planar graphs ♦ Planarity testing Abstract 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 $\textit{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 $\textit{O}(\textit{n}2/3)$ time, where $\textit{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: $\textit{O}(\textit{n}2/3)$ worst-case time per edge deletion, $\textit{O}(\textit{n}2/3)$ amortized time per edge insertion, and $\textit{O}(\textit{n}2/3)$ amortized time per edge insertion, and $\textit{O}(\textit{n}2/3)worst-case$ time to check whether two vertices are either biconnected or triconnected. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1999-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 46 Issue Number 1 Page Count 64 Starting Page 28 Ending Page 91

#### Open content in new tab

Source: ACM Digital Library