Partition planar graph into connected subgraphs of equal size

Question

Work

Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549.

states that for 4-edge-connected graph one can partition its edges into disjoint subsets of size $r,ドル such that each subset form a connected subgraph.

I wonder if the same kind of statement could be formulated for partition of vertices. For what kind of graphs one find partition of vertices into disjoint subsets of size $\approx r,ドル such that each subset form a connected subgraph (for each r)? I'm particularly interested in planar graphs, but would be happy with any class.

I can soften some conditions (it will still meet my needs): for what graph classes existence of partition into less than $\frac{\alpha n}{r}$ connected subgraphs of size less than $r$ is guaranteed (for some $\alpha$)?

• Pratik Deoghare: Compute planer embedding. Run some kind of sweep line algorithm. Once sweep line hits n/r vertices cut the edges connecting to the rest of the graph. This should work for planer graphs.
• ivmihajlin: Well, you can't do this partition for any planar graph: for example star-graph is planar, but it is impossible to cut it into pieces of size more then 1.
• Pratik Deoghare: I see. This makes the question very interesting. +1

Answer 1

Compute a constant degree spanning tree $T$ of your graph, root it, and now greedily find subtrees of roughly size $r,ドル extract them, and repeat. Naturally, if there is no constant degree spanning tree, then the star example shown above demonstrates that this algorithm can fail.

Answer 2

For a graph $G=(V,E),ドル deciding if $V$ can be partitioned into equal sized subsets (say, for a fixed size $r$) where each subset induces a connected subgraph is $\mathsf{NP}$-hard. It remains $\mathsf{NP}$-hard for planar graphs, and also if the number of subsets is fixed instead of the subset size ($|V|/r$ fixed).

However, the problem is polynomial for cycles, and thus for Hamiltonian graphs. It is also polynomial for trees and for series-parallel graphs when the number of subsets is fixed.

You can find these results in:

• M. E. Dyer and A. M. Frieze. On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics, 10(2), 139-153. 1985.

• N. Apollonio & al. Bicolored graph partitioning, or: gerrymandering at its worst. Discrete Applied Mathematics, 157(17), 3601-3614. 2009.

Edit (bis): (削除) I think that I was wrong about Hamiltonian graphs. They may be partitioned even if their Hamiltonian cycle cannot. Thus the problem can be not polynomial. (削除ここまで) See the first comment.

• ivmihajlin: Looks like you can do it for Hamiltonian graph. As this graph has a Hamiltonian graph, it has a spanning tree of max degree 2. It is possible to find a spanning tree of max degree 3 in polynomial time and using this tree partition the graph (as stated in other answer). research.microsoft.com/en-us/um/people/mohits/publications/…