# Optimal partitioning of a graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I would also like as much 'resolution' as possible - that is, I want to maximize the number of groups (minimize the number of nodes per group). Internal edges should be rewarded, to avoid long 'daisy chains' of nodes.

Does anyone have any suggestions as to how I can compute an (approximately) optimal solution? My instinct is to approach this using Monte Carlo, but I'm not sure how I would implement it here.

If all you're looking for is an approximate solution, I would suggest starting with one of the well-known graph partitioning packages, for example METIS. It allows you to attach weights to nodes. Partition it into $P$ groups and check whether your minimal weight sum condition is satisfied. If yes, try partitioning into $P+1$ groups and check again. Then repeat until one of your groups violates the minimal weight sum condition.