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...

Full description

Bibliographic Details

Published in:	Journal of the ACM 46, 1 (1999).
Main Author:	Galil, Zvi
Format:	Article
Language:	English
Subjects:	Theory of computation. Analysis of algorithms and problem complexity. Mathematics of computing. Discrete mathematics. Algorithms.