algorithms – Split a graph into 2 components of known distribution?

I'm trying to find a method to randomly split a connected planar graph $$G$$ in two related components, so that the number of vertices of each component is relatively close. In addition, I want to be able to calculate the probability that $$G$$ is divided into these two components by this method.

I've solved the problem if we do not care about the size of the components.

Simply create a uniformly random overlay tree of $$G$$, and randomly delete one of its edges, dividing it into two components $$A, B$$. Next, calculate the number of covering trees in each component and multiply it by the number of edges between $$A$$ and $$B$$, $$e (A, B)$$. This gives how many covering trees can possibly give $$G$$. In any overlapping tree, each edge gives a different division, and there is always $$(n-1)$$ possible edges that we can delete. So: $$p (A, B) = t (A) t (B) e (A, B) frac {1} {t (A cup B) (n-1)}$$

(The last part is not really necessary because it stays constant, I only need something proportional)

I am looking for an algorithm that can practically be done on relatively small graphs, with an order of about 50.

Posted on