Approximability of the genus problem What is currently known about the approximability of the genus problem? A preliminary search tells me that a constant factor approximation is trivial for sufficiently dense graphs, and an $n^\epsilon$-approximation algorithm has been ruled out. Is this information up-to-date, or are there better bounds known?
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.