some questions on MST

Question

I am learning the topic of Minimum-Spanning-Tree right now, and I understand the most of it, but I still have some things that I do not understand. I am dealing with undirected weighted graphs.

First, I know that finding MST costs O(E*log V). Now, I want to optimize it to linear time - O(V+E), when we dealing with planar graphs.

Secondly, I saw an example of n points in the unit-square and I succeed to show that a MST that weights O(sqrt n) is exist. The problem is that I could not find an algorithm to find this MST.

Thanks all, Or

Answer 1

Boruvka's algorithms runs in O(V) time on planar graphs. For details see

http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsII.pdf

Also, you can compute the Euclidean MST of n points in the plane in O(n log n) time by computing MST of edges in Delauney triangulation.