Separator based sparsification II: edge and vertex connectivity

David Eppstein,
Zvi Galil,
Giuseppe F. Italiano,
and Thomas H. Spencer

*SIAM J. Computing* 28(1):341–381, 1999

*Mathematical Reviews* 99g:05058, 1999

Reviewed by Fabrizio Luccio

A continuation of a series of basic contributions on dynamic graphs, produced by the same authors [see Part I, J. Comput. System Sci. 52 (1996), no. 1, 3--27; MR 97c:05052], this paper deals with the maintenance of a planar graph under insertion and deletion of edges. The main results are low-complexity amortized algorithms to retain information about vertex connectivity. Although the definition of planarity relies on the existence of a plane embedding, the authors devise techniques to keep the graph planar under edge insertion without reference to any embedding (which may in fact change). This is another significant contribution to the important field of plane graph algorithms, based on the concept of sparse certificate.