pdf icon
Volume 13 (2017) Article 5 pp. 1-47
APPROX-RANDOM 2013 Special Issue
A Pseudo-Approximation for the Genus of Hamiltonian Graphs
Received: October 1, 2013
Revised: May 15, 2017
Published: August 31, 2017
Download article from ToC site:
[PDF (599K)] [PS (3518K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: approximation algorithms, graph genus, Hamiltonian graphs
Categories: algorithms, approximation algorithms, graphs, graph algorithms, graph genus, graphs - Hamiltonian, special issue, APPROX, APPROX-RANDOM 2013 special issue
ACM Classification: F.2.2, G.2.2
AMS Classification: 68W25

Abstract: [Plain Text Version]

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