Weighted undirected graph partitioning

Question

Given an undirected cyclic planar graph G(V,E) with vertex weights W(V), a fixed plane embedding E(G) and two nodes s and t, I need to find a partitioning of G that divides it into two connected components S(G) and T(G) with s being in S(G) and t being in T(G). Vertices s and t both belong to the external face in the embedding E(G).

I wish to have the partitions well balanced - they should have nearly equal sums of vertex weights.

Any ideas for a good algorithm please?

Answer 1

It is some sort of balanced cut problem which is NP Complete in general and has logarithmic factor approximation algorithms. If im correct then it is weakly NP hard in planar graphs with 2 approx algorithm by naveen garg.(chk it on google)

Answer 2

Compute a Minimum Spanning Tree and use in conjunction with an AVL Tree balancing properties?