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.
