  We design the first subexponential-time (parameterized) algorithms for
several cut and cycle-hitting problems on $H$-minor free graphs. In particular,
we obtain the following results (where $k$ is the solution-size parameter).
  1. $2^{O(\sqrt{k}\log k)} \cdot n^{O(1)}$ time algorithms for Edge
Bipartization and Odd Cycle Transversal;
  2. a $2^{O(\sqrt{k}\log^4 k)} \cdot n^{O(1)}$ time algorithm for Edge
Multiway Cut and a $2^{O(r \sqrt{k} \log k)} \cdot n^{O(1)}$ time algorithm for
Vertex Multiway Cut, where $r$ is the number of terminals to be separated;
  3. a $2^{O((r+\sqrt{k})\log^4 (rk))} \cdot n^{O(1)}$ time algorithm for Edge
Multicut and a $2^{O((\sqrt{rk}+r) \log (rk))} \cdot n^{O(1)}$ time algorithm
for Vertex Multicut, where $r$ is the number of terminal pairs to be separated;
  4. a $2^{O(\sqrt{k} \log g \log^4 k)} \cdot n^{O(1)}$ time algorithm for
Group Feedback Edge Set and a $2^{O(g \sqrt{k}\log(gk))} \cdot n^{O(1)}$ time
algorithm for Group Feedback Vertex Set, where $g$ is the size of the group.
  5. In addition, our approach also gives $n^{O(\sqrt{k})}$ time algorithms for
all above problems with the exception of $n^{O(r+\sqrt{k})}$ time for
Edge/Vertex Multicut and $(ng)^{O(\sqrt{k})}$ time for Group Feedback
Edge/Vertex Set.
  We obtain our results by giving a new decomposition theorem on graphs of
bounded genus, or more generally, an $h$-almost-embeddable graph for any fixed
constant $h$. In particular we show the following. Let $G$ be an
$h$-almost-embeddable graph for a constant $h$. Then for every
$p\in\mathbb{N}$, there exist disjoint sets $Z_1,\dots,Z_p \subseteq V(G)$ such
that for every $i \in \{1,\dots,p\}$ and every $Z'\subseteq Z_i$, the treewidth
of $G/(Z_i\backslash Z')$ is $O(p+|Z'|)$. Here $G/(Z_i\backslash Z')$ is the
graph obtained from $G$ by contracting edges with both endpoints in $Z_i
\backslash Z'$.
