Theory of Computing ------------------- Title : A Pseudo-Approximation for the Genus of Hamiltonian Graphs Authors : Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos Volume : 13 Number : 5 Pages : 1-47 URL : https://theoryofcomputing.org/articles/v013a005 Abstract -------- The genus of a graph is a basic parameter in topological graph theory that has been the subject of extensive study. Perhaps surprisingly, despite its importance, the problem of approximating the genus of a graph is very poorly understood. Thomassen (1989) showed that computing the exact genus is NP-complete, and the best known upper bound for general graphs is an $O(n)$-approximation that follows by Euler's characteristic. We give a polynomial-time pseudo-approximation algorithm for the orientable genus of Hamiltonian graphs. More specifically, on input a graph $G$ of orientable genus $g$ and a Hamiltonian path in $G$, our algorithm computes a drawing on a surface of either orientable or non- orientable genus $O(g^{7})$. A preliminary version of this paper appeared in the Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2013).