  The Euler genus of a graph is a fundamental and well-studied parameter in
graph theory and topology. Computing it has been shown to be NP-hard by
[Thomassen '89 & '93], and it is known to be fixed-parameter tractable.
However, the approximability of the Euler genus is wide open. While the
existence of an O(1)-approximation is not ruled out, only an
O(sqrt(n))-approximation [Chen, Kanchi, Kanevsky '97] is known even in bounded
degree graphs. In this paper we give a polynomial-time algorithm which on input
a bounded-degree graph of Euler genus g, computes a drawing into a surface of
Euler genus poly(g, log(n)). Combined with the upper bound from [Chen, Kanchi,
Kanevsky '97], our result also implies a O(n^(1/2 - alpha))-approximation, for
some constant alpha>0.
  Using our algorithm for approximating the Euler genus as a subroutine, we
obtain, in a unified fashion, algorithms with approximation ratios of the form
poly(OPT, log(n)) for several related problems on bounded degree graphs. These
include the problems of orientable genus, crossing number, and planar edge and
vertex deletion problems. Our algorithm and proof of correctness for the
crossing number problem is simpler compared to the long and difficult proof in
the recent breakthrough by [Chuzhoy 2011], while essentially obtaining a
qualitatively similar result. For planar edge and vertex deletion problems our
results are the first to obtain a bound of form poly(OPT, log(n)).
  We also highlight some further applications of our results in the design of
algorithms for graphs with small genus. Many such algorithms require that a
drawing of the graph is given as part of the input. Our results imply that in
several interesting cases, we can implement such algorithms even when the
drawing is unknown.
