Obtaining Planarity by Contracting Few Edges
  The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by k. 
Petr A. Golovach, Pim van 't Hof, Daniel Paulusma
cs.DS cs.DM math.CO