Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus

Abstract: We give a constant factor approximation algorithm for
the asymmetric traveling salesman problem when the underlying
undirected graph of the Held-Karp linear programming relaxation
of the problem has bounded genus. Our result also implies the
weak version Goddyn's conjecture on the existence of thin trees
on graphs with bounded genus.