A note on approximating graph genus Academic Article uri icon

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.

published proceedings

  • Information Processing Letters

altmetric score

  • 5.488

author list (cited authors)

  • Chen, J., Kanchi, S. P., & Kanevsky, A.

citation count

  • 12

complete list of authors

  • Chen, Jianer||Kanchi, Saroja P||Kanevsky, Arkady

publication date

  • March 1997