Algorithm to find the minimum spanning tree on a planar graph

1. Dec 3, 2015

TheMathNoob

1. The problem statement, all variables and given/known data
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.

2. Relevant equations
m=edges
n=vertices

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))

3. 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.

2. Dec 4, 2015

andrewkirk

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.