Algorithm to find the minimum spanning tree on a planar graph

[TheMathNoob]

Homework Statement

I have the following algorithms: Prime MST with array, Prime MST with priorityq and Kruskal with priorityq. I have to choose the best algorithm to find the minimum spanning tree on a planar graph. A planar graph has the property in which the number of edges is in O(number of vertices). What does that mean?. The answer key says that kruskal is better.

Homework Equations

m=edges
n=vertices[/B]
Prime MST with array O(n^2+m)--> O(n^2)
Prime MST with pq: O(nlog(n)+mlog(n)) m>n O(mlogn)
Kruskal with pq: O(mlog(m))

The Attempt at a Solution

m in O(n) means to me that there is at most n number of edges and to me that looks weird because of the property of a maximal planar graph which says that at most a planar graph can have m= 3n-6 edges.

 

[andrewkirk]

A planar graph has the property in which the number of edges is in O(number of vertices).

I would take that to mean that there exists some real constant C such that for every ##n\in\mathbb{N}##, the number of edges of every planar graph with ##n## vertices is less than or equal to ##Cn##. It is not necessarily the case that ##C=1## as you have surmised in your last paragraph.