  We give the first polynomial-time approximation scheme (PTAS) for the Steiner
forest problem on planar graphs and, more generally, on graphs of bounded
genus. As a first step, we show how to build a Steiner forest spanner for such
graphs. The crux of the process is a clustering procedure called
prize-collecting clustering that breaks down the input instance into separate
subinstances which are easier to handle; moreover, the terminals in different
subinstances are far from each other. Each subinstance has a relatively
inexpensive Steiner tree connecting all its terminals, and the subinstances can
be solved (almost) separately. Another building block is a PTAS for Steiner
forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard
even on graphs of treewidth 3. Therefore, our PTAS for bounded treewidth graph
needs a nontrivial combination of approximation arguments and dynamic
programming on the tree decomposition. We further show that Steiner forest can
be solved in polynomial time for series-parallel graphs (graphs of treewidth at
most two) by a novel combination of dynamic programming and minimum cut
computations, completing our thorough complexity study of Steiner forest in the
range of bounded treewidth graphs, planar graphs, and bounded genus graphs.
