| Summary: | Abstract: "It is known that tembedding 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[superscript epsilon]), 0 [< or =] [epsilon] < 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."
|
|---|