Mathematical Reviews 97c:05052

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.

Fano Experimental Web Server, D. Eppstein, School of Information & Computer Science, UC Irvine
Made on a Mac Valid XHTML 1.0!