Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total of O(n log n) time under any sequence of at most O(n) deletions. This gives O(log n) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O(n log2 n) time. This gives O(log2 n) amortized time per deletion. The space required by all our data structures is O(n). All our time bounds improve previous bounds.
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Sankar Basu
Journal of the Franklin Institute
Andrew Skumanich
SPIE Optics Quebec 1993
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences