Approximating the genus of dense graphs

Determining the genus of graphs is one of the fundamental NP-complete problems. Thus it makes sense to ask whether the genus can be efficiently approximated. By using the Szemeredi Regularity Lemma, and by analysing the genus of random and quasirandom graphs, we are able to find a PTAS (polynomial-time approximation scheme) to approximate the genus of dense graphs within arbitrarily small error.

This is joint work with Yifan Jing.