A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs | Algorithmica Skip to main content
Springer Nature Link
Log in

A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We give a linear time and space algorithm for analyzing trees in planar graphs. The algorithm can be used to analyze the sensitivity of a minimum spanning tree to changes in edge costs, to find its replacement edges, and to verify its minimality. It can also be used to analyze the 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 planar embedding, combined with a heap-ordered queue data structure.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJ. Comput. System Sci., 13:335–379, 1976.

    Google Scholar 

  2. D. Cheriton and R. E. Tarjan. Finding minimum spanning trees.SIAM J. Comput., 5:724–742, 1976.

    Google Scholar 

  3. N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ-trees.J. Comput. System Sci., 30:54–76, 1985.

    Google Scholar 

  4. B. Dixon, M. Rauch, and R. E. Tarjan. Verification and sensitivity analysis of minimum spanning trees in linear time.SIAM J. Comput., 21:1184–1192, 1992.

    Google Scholar 

  5. D. Eppstein. Finding thek smallest spanning trees.Proc. 2nd Scandinavian Workshop on Algorithm Theory (SWAT 90), Lecture Notes in Computer Science, Vol. 447, pp. 38–47. Springer-Verlag, Berlin, 1990.

    Google Scholar 

  6. D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, and M. Yung. Maintenance of a minimum spanning forest in a dynamic planar graph.J. Algorithms, 13:33–54, 1992.

    Google Scholar 

  7. G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications.SIAM J. Comput., 14:781–798, 1985.

    Google Scholar 

  8. H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking.Proc. 1st ACM-SIAM Symposium on Discrete Algorithms, pp. 434–443, 1990.

  9. H. N. Gabow and M. Stallmann. Efficient algorithms for graphic matroid intersection and parity (extended abstract). InAutomata, Languages, and Programming, 12th Colloquium, Lecture Notes in Computer Science, Vol. 194, pp. 210–220. Springer-Verlag, Berlin, 1985.

    Google Scholar 

  10. H. Gajewska and R. E. Tarjan. Deques with heap order.Inform. Process. Lett., 22:197–200, 1986.

    Google Scholar 

  11. D. Gusfield. A note on arc tolerances in sparse shortest path and network flow problems.Networks, 13:191–196, 1983.

    Google Scholar 

  12. F. Harary.Graph Theory. Addison-Wesley, Reading, MA, 1972.

    Google Scholar 

  13. J. Hopcroft and R. E. Tarjan. Efficient planarity testing.J. Assoc. Comput. Mach., 21:549–568, 1974.

    Google Scholar 

  14. R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs.SIAM J. Appl. Math., 36:177–189, 1979.

    Google Scholar 

  15. D. R. Shier and G. Witzgall. Arc tolerances in shortest path and network flow problems.Networks, 10:277–291, 1980.

    Google Scholar 

  16. R. E. Tarjan. Depth first search and linear graph algorithms.SIAM J. Comput., 1:146–160, 1972.

    Google Scholar 

  17. R. E. Tarjan. Finding dominators in directed graphs.SIAM J. Comput., 3:62–89, 1974.

    Google Scholar 

  18. R. E. Tarjan. Applications of path compression on balanced trees.J. Assoc. Comput. Mach., 26:690–715, 1979.

    Google Scholar 

  19. R. E. Tarjan. Sensitivity analysis of minimum spanning trees and shortest path trees.Inform. Process. Lett., 14:30–33, 1982.

    Google Scholar 

  20. W. T. Tutte.Graph Theory. Addison-Wesley, Menlo Park, CA, 1984.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Tennessee, 37996, Knoxville, TN, USA

    Heather Booth

  2. Department of Computer Science, Yale University, 06520-2158, New Haven, CT, USA

    Jeffery Westbrook

Authors
  1. Heather Booth
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jeffery Westbrook
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by Harold N. Gabow.

This research was partially supported by Office of Naval Research Grant N00014-87-K-0467 and National Science Foundation Grant CCR-8610181.

This research was done while the author was at the Department of Computer Science, Princeton University, Princeton, NJ 08544, USA.

This research was done while the author was at the Department of Computer Science, Stanford University, Stanford, CA 94305, USA.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Booth, H., Westbrook, J. A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs. Algorithmica 11, 341–352 (1994). https://doi.org/10.1007/BF01187017

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01187017

Key words

Search

Navigation