  The Multicut problem asks for a minimum cut separating certain pairs of
vertices: formally, given a graph $G$ and demand graph $H$ on a set $T\subseteq
V(G)$ of terminals, the task is to find a minimum-weight set $C$ of edges of
$G$ such that whenever two vertices of $T$ are adjacent in $H$, they are in
different components of $G\setminus C$. Colin de Verdi\`{e}re [Algorithmica,
2017] showed that Multicut with $t$ terminals on a graph $G$ of genus $g$ can
be solved in time $f(t,g)n^{O(\sqrt{g^2+gt+t})}$. Cohen-Addad et al. [JACM,
2021] proved a matching lower bound showing that the exponent of $n$ is
essentially best possible (for fixed values of $t$ and $g$), even in the
special case of Multiway Cut, where the demand graph $H$ is a complete graph.
  However, this lower bound tells us nothing about other special cases of
Multicut such as Group 3-Terminal Cut. We show that if the demand pattern is,
in some sense, close to being a complete bipartite graph, then Multicut can be
solved faster than $f(t,g)n^{O(\sqrt{g^2+gt+t})}$, and furthermore this is the
only property that allows such an improvement. Formally, for a class
$\mathcal{H}$ of graphs, Multicut$(\mathcal{H})$ is the special case where the
demand graph $H$ is in $\mathcal{H}$. For every fixed class $\mathcal{H}$
(satisfying some mild closure property), fixed $g$, and fixed $t$, our main
result gives tight upper and lower bounds on the exponent of $n$ in algorithms
solving Multicut$(\mathcal{H})$.
  In addition, we investigate a similar setting where, instead of
parameterizing by the genus $g$ of $G$, we parameterize by the minimum number
$k$ of edges of $G$ that need to be deleted to obtain a planar graph.
Interestingly, in this setting it makes a significant difference whether the
graph $G$ is weighted or unweighted: further nontrivial algorithmic techniques
give substantial improvements in the unweighted case.
