# Dividing a weighted planar graph into $k$ subgraphs with balanced weight

I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge weights. After cutting, each subgraph must be connected (i.e. there must be a path between any two vertices of the subgraph which is only composed of vertices in that subgraph).

However, unlike most existing work on graph partitioning out there, I don't intend to obtain subgraphs that contain the same approximate number of vertices. Instead, I would like these subgraphs to have similar sum of edge weights. In other words, I would like to minimize the sum of edge weights of the subgraph with maximal weight and ideally cut long (weighted) edges.

Is there a name for this problem? I wasn't able to find anything about this on the web. Also, how can I approach this problem?

• Are there no constraints on the size of the subgraph? Say a minimum of 2 vertices in the subgraphs or else the problem could have a trivial answer like each vertex forms a graph with zero total weight. – swarnim_narayan Aug 2 '13 at 11:25
• @wang if $k$ is fixed, separate each vertex doesn't work. – wece Aug 2 '13 at 11:41
• You only care for the existence of such a subgraph, and not for a solution that minimizes the sum of deleted edges or the weight (in terms of edge weights) of each connected component? Also, are the weights in a specific range, or can they be arbitrarily large? – Jonas G. Drange Aug 4 '13 at 10:08
• @JonasG.Drange: the goal is to find a cut, where the weight of the subgraph with maximum weight is minimized. The weights are arbitrary real positive numbers. Thanks! – davidbsp Aug 4 '13 at 21:12
• how many edges am I allowed to cut? can I also cute edges within a subgraph, if it still remains connected afterwards? – Syzygy Sep 22 '16 at 23:43