Finding Minimum Spanning Trees

This paper studies methods for finding minimum spanning trees in graphs. Results include 1. several algorithms with O (m n) worst-case running times, where n is the number vertices and m is the number of edges in the problem graph; 2. an O (m) worst-case algorithm for dense graphs (those for which m is (n^1 +) for some positive constant) ; 3. an O (n) worst-case algorithm for planar graphs; 4. relationships with other problems which might lead general lower bound for the complexity of the minimum spanning tree problem.