Department of

January 2014 February 2014 March 2014 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 1 1 5 6 7 8 9 10 11 2 3 4 5 6 7 8 2 3 4 5 6 7 8 12 13 14 15 16 17 18 9 10 11 12 13 14 15 9 10 11 12 13 14 15 19 20 21 22 23 24 25 16 17 18 19 20 21 22 16 17 18 19 20 21 22 26 27 28 29 30 31 23 24 25 26 27 28 23 24 25 26 27 28 29 30 31

Monday, February 3, 2014

**Abstract:** The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard [Thomassen 1989, 1993], and it is known to be fixed-parameter tractable; that is, for each fixed constant g, there is a polynomial time algorithm that decides whether a given graph G has Euler genus at most g. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(sqrt(n))-approximation is known [Chen, Kanchi, and Kanevsky, 1997] even in bounded degree graphs. In this paper we give a polynomial-time algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus g^O(1) * log^O(1) n. Combined with the upper bound from [Chen, Kanchi, and Kanevsky, 1997], our result also implies a O(n^(1/2 - alpha)-approximation, for some constant alpha>0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPT^O(1) * log^O(1) n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. The talk will focus on the high-level tools for the genus computation coming from the seminal work on graph minors by Robertson and Seymour. Joint work with Anastasios Sidiropoulos.