Polylogarithmic approximation for minimum planarization (almost)

Ken-ichi Kawarabayashi, Anastasios Sidiropoulos

In the minimum planarization problem, given some $n$-vertex graph, the goal is to find a set of vertices of minimum cardinality whose removal leaves a planar graph. This is a funda…