I am looking for an algorithm that, given an undirected, planar graph $G = (V,E)$ with node weights, meets the following conditions:Creates balanced (within some margin) $k$ partitions of $V$ according to node weight.All partitions have to be connected.It cannot minimize communication volume, or edge cuts.My graphs are planar, all vertex weights are positive integers, and the reason that I want #3 is that I need to be able to generate $n$ distinct partitions from the graph that I have. I have found that if I use GPMetis, no matter what options and seed I pass it (currently using -seed=40 -ctype=rm -iptype=random -ptype=kway). The options have an impact only if I scale up the number of vertexes (on my graphs that have less than 100 nodes, it always gives the same answer).Are there algorithms that exist to create balanced partitions by vertex weight that meet these conditions? It doesn't need to ignore edge counts/weight entirely, so long as I can still make the result different via some seed. Willing to take either a research paper, or fully functional code.As background: I know that a vertex separator can be found in polynomial time for planar graphs, but I need all my vertices. There are several edge cut algorithms that also run in near polynomial time, but these have the problem listed above of not being able to inject sufficient randomness.
Partitioning planar graphs without minimizing edge cuts
algorithms;graphs;optimization;partition problem;planar graphs