The Approximability of Graph Minimum Genus Embeddings

Let genus_min(G) denote the minimum genus of the graph G. For an orientable embedding rho(G) of G, let genus(rho(G)) denote the genus of the embedding. An approximation algorithm M for graph minimum genus embeddings is one that constructs an embedding rho_M(G) given a graph G. We say that the algorithm M has an approximation ratio r if for all graphs genus(rho_M(G)) / genus_min(G) is at most r.

Question: Does there exist a polynomial-time approximation algorithm of ratio c for graph minimum genus embeddings, where c is a fixed constant?

It is known that constructing graph minimum genus embeddings is NP-hard. For a fixed genus g, there is a linear-time algorithm that given a graph either constructs an embedding of genus at most g for the graph or reports no such an embedding exists.

In [CKK], we showed that unless P = NP, for any epsilon < 1, there is no polynomial-time algorithm that for any graph G constructs an embedding rho(G) such that the difference genus(rho(G)) - genus_min(G) is always less than n^epsilon. Moreover, new techniques have been recently developed to show that many related graph problems, such as graph coloring problem and longest cycle problem, have no polynomial time approximation algorithms with a constant ratio (assuming P does not equal NP).

A simple combinatorial analysis shows that for a graph G, if the number of edges is at least 4 times the number of vertices, then the genus of any embedding of the graph G is at most 9 times the minimum genus of the graph. Therefore, the harder part of the problem is to approximate minimum genus embeddings of ``sparse graphs''.

References:

[CKK] J. Chen, S. P. Kanchi, and A. Kanevsky, On the complexity of graph embeddings, Lecture Notes in Computer Science 709 (1993), 234-245.

Submitted by: Jianer Chen, Department of Computer Science, Texas A\&M University, College Station, Texas 77843-3112.