  We prove essentially tight lower bounds, conditionally to the Exponential
Time Hypothesis, for two fundamental but seemingly very different cutting
problems on surface-embedded graphs: the Shortest Cut Graph problem and the
Multiway Cut problem. A cut graph of a graph $G$ embedded on a surface $S$ is a
subgraph of $G$ whose removal from $S$ leaves a disk. We consider the problem
of deciding whether an unweighted graph embedded on a surface of genus $g$ has
a cut graph of length at most a given value. We prove a time lower bound for
this problem of $n^{\Omega(g/\log g)}$ conditionally to ETH. In other words,
the first $n^{O(g)}$-time algorithm by Erickson and Har-Peled [SoCG 2002,
Discr.\ Comput.\ Geom.\ 2004] is essentially optimal. We also prove that the
problem is W[1]-hard when parameterized by the genus, answering a 17-year old
question of these authors. A multiway cut of an undirected graph $G$ with $t$
distinguished vertices, called terminals, is a set of edges whose removal
disconnects all pairs of terminals. We consider the problem of deciding whether
an unweighted graph $G$ has a multiway cut of weight at most a given value. We
prove a time lower bound for this problem of $n^{\Omega(\sqrt{gt +
g^2+t}/\log(g+t))}$, conditionally to ETH, for any choice of the genus $g\ge0$
of the graph and the number of terminals $t\ge4$. In other words, the algorithm
by the second author [Algorithmica 2017] (for the more general multicut
problem) is essentially optimal; this extends the lower bound by the third
author [ICALP 2012] (for the planar case). Reductions to planar problems
usually involve a grid-like structure. The main novel idea for our results is
to understand what structures instead of grids are needed if we want to exploit
optimally a certain value $g$ of the genus.
