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...
| Cyhoeddwyd yn: | Journal of the ACM 46, 1 (1999). |
|---|---|
| Prif Awdur: | |
| Fformat: | Erthygl |
| Iaith: | English |
| Pynciau: |