Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph

Report ID: TR-243-90

---

Author: Eppstein, David / Tarjan, Robert E. / Westbrook, Jeffrey / Italiano, Guiseppe F. / Tamassia, Roberto / Yung, Moti

---

Date: 1990-01-00

---

Pages: 30

---

Download Formats: |PDF|

---

Abstract:

We give effcient algorithms for maintaining a minimum spanning forest of a planar graph subject to on-line modifications. The modifications supported include changes in the edge weights, and insertion.