A LINEAR ALGORITHM FOR ANALYSIS OF MINIMUM SPANNING AND SHORTEST-PATHTREES OF PLANAR GRAPHS

We give a linear time and space algorithm for analyzing trees in plana r graphs. The algorithm can be used to analyze the sensitivity of a mi nimum spanning tree to changes in edge costs. to find its replacement edges, and to verify its minimality. It can also be used to analyze th e sensitivity of a single-source shortest-path tree to changes in edge costs, and to analyze the sensitivity of a minimum-cost network flow. The algorithm is simple and practical. It uses the properties of a pl anar embedding, combined with a heap-ordered queue data structure.