1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm to find the minimum spanning tree on a planar graph

  1. Dec 3, 2015 #1
    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. jcsd
  3. Dec 4, 2015 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Algorithm to find the minimum spanning tree on a planar graph
Loading...