On wikipedia it says that boruvka can be implemented in linear time for planar graphs, but I don't know how to prove that.

  • 1
    $\begingroup$ Wikipedia also seems to give a big hint for how one could do that. Did you try removing all but the cheapest edge between each pair of components after each stage of the algorithm? $\endgroup$
    – Juho
    Dec 10 '20 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.