Fully dynamic planarity testing with applications.
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, w...
| Publicat a: | Journal of the ACM 46, 1 (1999). |
|---|---|
| Autor principal: | |
| Format: | Article |
| Idioma: | English |
| Matèries: |