# Partition planar graph into connected subgraphs of equal size

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$)?

• 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. Aug 19, 2014 at 21:40
• 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. Aug 20, 2014 at 0:57
• I see. This makes the question very interesting. +1 Aug 20, 2014 at 1:35

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.
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).