<p>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. </p>

CC BY-SA 3.0
2014-08-20T03:16:07.820Z
2014-08-20T03:16:07.820Z
Sariel Har-Peled
<p>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).</p>

<p>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.</p>

<p>You can find these results in:</p>

<ul>
<li><p>M. E. Dyer and A. M. Frieze. <a href="http://math.cmu.edu/~af1p/Texfiles/COMPLEXPART.pdf" rel="noreferrer">On the complexity of partitioning graphs into connected subgraphs</a>.  Discrete Applied Mathematics, 10(2), 139-153. 1985.</p></li>
<li><p>N. Apollonio &amp; al. <a href="http://www.sciencedirect.com/science/article/pii/S0166218X09002637" rel="noreferrer">Bicolored graph partitioning, or: gerrymandering at its worst</a>.  Discrete Applied Mathematics, 157(17), 3601-3614. 2009.</p></li>
</ul>

<p>Edit (bis): <s>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.</s> See the first comment.</p>

CC BY-SA 3.0
2014-08-20T21:33:07.207Z
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).

http://research.microsoft.com/en-us/um/people/mohits/publications/approximating_minimum_bounded_degree_spanning_tree_to_within_one_of_optimal.pdf
ivmihajlin
CC BY-SA 3.0
2014-08-20T09:22:44.517Z
2014-08-21T08:19:52.840Z
2014-08-21T08:19:52.840Z
Lamine
<p>Work </p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2014-08-19T21:40:40.257Z
Compute planer embedding. Run some kind of [sweep line algorithm](https://en.wikipedia.org/wiki/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.
Pratik Deoghare
CC BY-SA 3.0
2014-08-20T00:57:20.273Z
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.
ivmihajlin
CC BY-SA 3.0
2014-08-20T01:35:23.630Z
I see. This makes the question very interesting. +1
Pratik Deoghare
<graph-theory><planar-graphs><partition-problem>
Partition planar graph into connected subgraphs of equal size
ivmihajlin
# Partition planar graph into connected subgraphs of equal size

(Asked by: username_0 on 2014-08-19)

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

**Tags:** graph-theory, planar-graphs, partition-problem

> **Comments:**
> **username_1**: Compute planer embedding. Run some kind of [sweep line algorithm](https://en.wikipedia.org/wiki/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.  
> **username_0**: 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.  
> **username_1**: I see. This makes the question very interesting. +1  

---

## 2 answers

### Answer by username_2 on 2014-08-20. Score: 4 | Accepted answer

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 by username_3 on 2014-08-20. Score: 9

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](http://math.cmu.edu/~af1p/Texfiles/COMPLEXPART.pdf). Discrete Applied Mathematics, 10(2), 139-153. 1985.
* N. Apollonio & al. [Bicolored graph partitioning, or: gerrymandering at its worst](http://www.sciencedirect.com/science/article/pii/S0166218X09002637). 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.

> **Comments:**
> **username_0**: 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).  http://research.microsoft.com/en-us/um/people/mohits/publications/approximating_minimum_bounded_degree_spanning_tree_to_within_one_of_optimal.pdf  

---

