  We propose polynomial-time algorithms that sparsify planar and bounded-genus
graphs while preserving optimal or near-optimal solutions to Steiner problems.
Our main contribution is a polynomial-time algorithm that, given an unweighted
graph $G$ embedded on a surface of genus $g$ and a designated face $f$ bounded
by a simple cycle of length $k$, uncovers a set $F \subseteq E(G)$ of size
polynomial in $g$ and $k$ that contains an optimal Steiner tree for any set of
terminals that is a subset of the vertices of $f$.
  We apply this general theorem to prove that: * given an unweighted graph $G$
embedded on a surface of genus $g$ and a terminal set $S \subseteq V(G)$, one
can in polynomial time find a set $F \subseteq E(G)$ that contains an optimal
Steiner tree $T$ for $S$ and that has size polynomial in $g$ and $|E(T)|$; * an
analogous result holds for an optimal Steiner forest for a set $S$ of terminal
pairs; * given an unweighted planar graph $G$ and a terminal set $S \subseteq
V(G)$, one can in polynomial time find a set $F \subseteq E(G)$ that contains
an optimal (edge) multiway cut $C$ separating $S$ and that has size polynomial
in $|C|$.
  In the language of parameterized complexity, these results imply the first
polynomial kernels for Steiner Tree and Steiner Forest on planar and
bounded-genus graphs (parameterized by the size of the tree and forest,
respectively) and for (Edge) Multiway Cut on planar graphs (parameterized by
the size of the cutset). Additionally, we obtain a weighted variant of our main
contribution.
