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.

Send comments to *dan.archdeacon@uvm.edu *

August, 1995