On the complexity of graph embeddings
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
Springer-Verlag Berlin Heidelberg 1993. It is known that embedding a graph G into a surface of minimum genus min(G) is NP-hard, whereas embedding a graph G into a surface of maximum genus m(G) can be done in polynomial time. However, the complexity of embedding a graph G into a surface of genus between min(G) and m(G) is still unknown. In this paper, it is proved that for any function f(n)=O(n), 0 <1, the problem of embedding a graph G of n vertices into a surface of genus at most min(G)+f(n) remains NP-hard, while there is a linear time algorithm that approximates the minimum genus embedding either within a constant ratio or within a difference O(n). A polynomial time algorithm is also presented for embedding a graph G into a surface of genus M(G)-1.
