Polylogarithmic approximation for Euler genus on bounded degree graphs

Computing the Euler genus of a graph is a fundamental problem in algorithmic graph theory. It has been shown to be NP-hard by [Thomassen ’89, Thomassen ’97], even for cubic graphs, 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 an O (1)-approximation is not ruled out, the currently best-known upper bound is a O ( n 1−α )-approximation, for some universal constant α>0 [Kawarabayashi and Sidiropoulos 2017]. We present an O (log 2.5 n )-approximation polynomial time algorithm for this problem on graphs of bounded degree. Prior to our work, the best known result on graphs of bounded degree was a n Ω(1) -approximation [Chekuri and Sidiropoulos 2013]. As an immediate corollary, we also obtain improved approximation algorithms for the crossing number problem and for the minimum vertex planarization problem, on graphs of bounded degree. Specifically, we obtain a polynomial-time O ( 2 log 3.5 n )-approximation algorithm for the minimum vertex planarization problem, on graphs of maximum degree . Moreover we obtain an algorithm which given a graph of crossing number k , computes a drawing with at most k 2 log O (1) n crossings in polynomial time. This also implies a n 1/2 log O (1) n -approximation polynomial time algorithm. The previously best-known result is a polynomial time algorithm that computes a drawing with k 10 log O (1) crossings, which implies a n 9/10 log O (1) n -approximation algorithm [Chuzhoy 2011].

Authors

• Ken-ichi Kawarabayashi
• Anastasios Sidiropoulos

Keywords

• approximation algorithms
• crossing number
• graph genus