Beyond the Euler Characteristic
Ken‐ichi Kawarabayashi, Anastasios Sidiropoulos · 2015
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 [27] and a linear-time fixed-parameter algorithm has been obtained by Mohar [20]. Despite extensive study, the approximability of the Euler genus remains wide open. While the existence of a constant factor 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.