Separator based sparsification I: planarity testing and minimum spanning trees

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

*J. Computer & Systems Sciences* 52(1):3–27, Feb 1996

*Mathematical Reviews* 97c:05052, 1997

Reviewed by Fabrizio Luccio

Based on the fundamental sparsification technique devised by Eppstein, Galil, Italiano and Nissenzweig for the design of dynamic graph algorithms, this paper shows how a planar graph can be efficiently processed under the insertions and deletions of edges that preserve planarity. Although the definition of planarity crucially relies on the concept of plane embedding, the present technique is applied independently of the embedding, which may be altered by the graph changes. The major results are a fully dynamic planarity test working in $O(n^{1/2})$ amortized time per update or query, where $n$ is the number of vertices, and various efficient dynamic algorithms to maintain connected components, minimum spanning forests, and 2-edge-connected components, all valid for planar graphs. As an overall comment, this is a significant and useful addition to the algorithmic theory of planar graphs.