  We consider the problem of generating uniformly random partitions of the
vertex set of a graph such that every piece induces a connected subgraph. For
the case where we want to have partitions with linearly many pieces of bounded
size, we obtain approximate sampling algorithms based on Glauber dynamics which
are fixed-parameter tractable with respect to the bandwidth of $G$, with
simple-exponential dependence on the bandwidth. For example, for rectangles of
constant or logarithmic width this gives polynomial-time sampling algorithms.
More generally, this gives sub-exponential algorithms for bounded-degree graphs
without large expander subgraphs (for example, we obtain $O(2^{\sqrt n})$ time
algorithms for square grids).
  In the case where we instead want partitions with a small number of pieces of
linear size, we show that Glauber dynamics can have exponential mixing time,
even just for the case of 2 pieces, and even for 2-connected subgraphs of the
grid with bounded bandwidth.
