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...
| 发表在: | Journal of the ACM 46, 1 (1999). |
|---|---|
| 主要作者: | |
| 格式: | 文件 |
| 语言: | English |
| 主题: |