**Maintenance of a minimum spanning forest in a dynamic plane graph**.

D. Eppstein, G.F. Italiano, R. Tamassia, R.E. Tarjan, J. Westbrook, and M. Yung.

*1st ACM-SIAM Symp. Discrete Algorithms,*San Francisco, 1990, pp. 1–11.

*J. Algorithms*13 (1): 33–54, 1992 (special issue for 1st Symp. Discrete Algorithms).

Corrigendum,*J. Algorithms*15: 173, 1993.The complement of a minimum spanning tree is a maximum spanning tree in the dual graph. By applying this fact we can use a modified form of Sleator and Tarjan's dynamic tree data structure to update the MST in logarithmic time per update.

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.