  We present a novel space-efficient graph coarsening technique for $n$-vertex
planar graphs $G$, called cloud partition, which partitions the vertices $V(G)$
into disjoint sets $C$ of size $O(\log n)$ such that each $C$ induces a
connected subgraph of $G$. Using this partition $P$ we construct a so-called
structure-maintaining minor $F$ of $G$ via specific contractions within the
disjoint sets such that $F$ has $O(n/\log n)$ vertices. The combination of $(F,
P)$ is referred to as a cloud decomposition.
  For planar graphs we show that a cloud decomposition can be constructed in
$O(n)$ time and using $O(n)$ bits. Given a cloud decomposition $(F, P)$
constructed for a planar graph $G$ we are able to find a balanced separator of
$G$ in $O(n/\log n)$ time. Contrary to related publications, we do not make use
of an embedding of the planar input graph. We generalize our cloud
decomposition from planar graphs to $H$-minor-free graphs for any fixed graph
$H$. This allows us to construct the succinct encoding scheme for
$H$-minor-free graphs due to Blelloch and Farzan (CPM 2010) in $O(n)$ time and
$O(n)$ bits improving both runtime and space by a factor of $\Theta(\log n)$.
  As an additional application of our cloud decomposition we show that, for
$H$-minor-free graphs, a tree decomposition of width $O(n^{1/2 + \epsilon})$
for any $\epsilon > 0$ can be constructed in $O(n)$ bits and a time linear in
the size of the tree decomposition. Finally, we implemented our cloud
decomposition algorithm and experimentally verified its practical effectiveness
on both randomly generated graphs and real-world graphs such as road networks.
The obtained data shows that a simplified version of our algorithms suffices in
a practical setting, as many of the theoretical worst-case scenarios are not
present in the graphs we encountered.
