Partitioning planar graphs without minimizing edge cuts
One general method is to perturb the node weights slightly, find a good partition, and repeat that $n$ times with $n$ different perturbations.

The basic algorithm is something like this:


Repeat until you have $n$ distinct balanced partitions of $G$:


Copy $G$ to $G'$.  Randomly perturb the weight of each node in $G'$ by a tiny amount (a different random change for each node).
Find a balanced partition of $G'$.  This corresponds to a partition of $G$.
If this is a legal, balanced partition of $G$ and you haven't seen this partition of $G$ before, add it to your list of distinct partitions.



If you choose the amount of the perturbation correctly, then you can expect this will need only $O(n)$ iterations of the loop to find $n$ distinct partitions.

Let's see in a little more detail how to make this work in your setting and why it works.  The basic idea is to add a tiny, tiny random perturbation to each node's weight.  This won't affect the total weight of any group in your partition by very much: the sum of a bunch of of tiny numbers is still quite small, and in particular, we can ensure it will be much smaller than 1.  Since the total weight of any group of vertices in $G$ has to be an integer, the change in its total weight can't be enough to make it jump up to the next integer.   Consequently, this won't change the relative order of vertex-groups (if one vertex-group has a smaller weight than another vertex-group, after perturbation its weight cannot become larger); all it can do is break ties.

However, this basic idea has a problem: after perturbation, the vertex weights in $G'$ are no longer integers.  It's possible that your underlying algorithm (e.g., Metis) requires the vertex weights to be integers.   If so, here is how we can fix things up and preserve the integrality of node weights.  The idea is to first scale up all of the weights by a large integer constant $c_1$, then add a small integer perturbation to each node weight.  Formally, let $w_v$ be the weight on node $v$.  We're going to pick integer constants $c_1,c_2$ and for each node $v$ set

$$w'_v = c_1 w_v + r_v,$$

where $r_v$ is a random integer chosen from $\{0,1,\dots,c_2\}$ (chosen independently for each node).  We'll use $w'_v$ as the weight of node $v$ in $G'$.

How do we choose $c_1,c_2$?  Basically, we need $c_2$ to be large enough so that each iteration is likely to give you a new partition, and we need $c_1/c_2$ large enough so that a balanced partition of $G'$ is likely to also be a balanced partition of $G$.  One reasonable setting is to use $c_2=100n$ and $c_1 = 100 |V| c_2$.  Alternatively, if your underlying algorithm is OK with non-integer vertex weights, you could instead pick $r_v$ randomly from the range $[0,1/(100|V|)]$ and just leave $c_1=1$.

Why does this work?  Well, first note if we divide all the weights in a graph by a constant, that has no effect on the set of balanced partitions -- so we might as well consider the weights to be $w''_v = w_v + r_v/c_1$.  Now I claim that a balanced partition of $G'$ is almost certainly a balanced partition of $G$.  Any single group in the partition has at most $|V|$ vertices, and the weight of each node in the group has been randomly increased by at most $c_2/c_1$, so the total increase in the weight of that group is at most $|V|c_2/c_1=0.01$.  Originally the total weight of a vertex-group has to be integer, so this perturbation is not enough to make it jump up to the next integer.  Now, depending upon your definition of balanced, most likely the following will be true: any balanced partition in $G'$ has a high probability of being a balanced partition in $G$.

Also, the random perturbations ensure that, if you look at two perturbed graphs $G'_1,G'_2$, it is unlikely that the optimum partition of $G'_1$ is the same as the optimum partition of $G'_2$.

So, I suggest you give this a try.



Important caveats: There are no guarantees this will work.  From a theoretical perspective, it's not guaranteed to work.  Indeed, I suspect your problem might be NP-hard, so it would be too much to expect this to always work.  But in practice, this often works, if you are in a situation where your underlying algorithm (e.g., Metis) is able to find the optimum partition in a reasonable amount of time.  As a pragmatic guideline, it's more likely to work if the underlying algorithm can find an exact optimum rather than an approximate-optimum (e.g., maximally balanced rather than close-to-maximally-balanced).  However, as I said, there are no guarantees, so the best way to find out whether it will work in your particular situation is to try it out and see.