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).