A note on approximating graph genus
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
This note, using simple combinatorial analysis, shows two interesting facts on the approximability of graph minimum genus embeddings: (1) for any function f(n) = O(n), 0 < 1, there is no polynomial time algorithm that embeds a graph G of n vertices into a surface of genus bounded by min (G) + f(n), unless P = NP; and (2) there is a linear time algorithm that embeds a graph G of n vertices into a surface of genus bounded by max{4 min (G), min (G) + 4n}, where min (G) denotes the minimum genus of the graph G. An approximation algorithm with approximation ratio O(n) for bounded degree graph embeddings is also presented.