Beyond the Euler characteristic: Approximating the genus of general graphs

EADS talk by Ken-ichi Kawarabayashi, Professor, National Institute of Informatics and JST ERATO Kawarabayashi Project.

Ken-ichi Kawarabayashi

Abstract: Computing the Euler genus of a graph is a fundamental problem in graph theory and topology. It has been shown to be NP-hard by [Thomassen '89] and a linear-time fixed-parameter algorithm has been obtained by [Mohar '99]. Despite extensive study, the approximability of the Euler genus remains wide open. While the existence of O(1)-approximation is not ruled out, the currently best-known upper bound is a trivial O(n/g)-approximation that follows from bounds on the Euler characteristic.

In this paper, we give the first non-trivial approximation algorithm for this problem. Specifically, we give an O(n^{1-c}) approximation algorithm for some constant c.

Our approximation algorithm also has implications for the design of algorithms on graphs of small genus. Several of these algorithms require that an embedding of the graph into a surface of small genus is given as part of the input. Our result implies that many of these algorithms can be implemented even when the embedding of the input graph is unknown.

Joint work with Anastasios Sidiropoulos.