Polylogarithmic approximation for Euler genus on bounded degree graphs
Ken‐ichi Kawarabayashi, Anastasios Sidiropoulos · 2019
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(n1−α)-approximation, for some universal constant α>0 [Kawarabayashi and Sidiropoulos 2017].