Approximability of the genus problem
The best published results all appear in a 1997 paper by Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky.


For any fixed $\varepsilon&gt;0$, computing the genus of a graph with additive error $O(n^\varepsilon)$ is NP-hard.
There is a trivial linear-time algorithm to embed any $n$-vertex graph of (unknown) genus $g$ on an orientable surface of genus $\max\{4g, g+4n\}$: Assign an arbitrary cyclic order to the edges leaving each vertex (keeping loops and parallel edges together).  In other words, when the genus is large, every embedding is a good approximation of the best embedding.
There is a polynomial-time $O(\sqrt{n})$-approximation algorithm for bounded-degree graphs.


It is an open question whether there is an efficient constant-factor approximation algorithm.