Obtaining planarity by contracting few edgesPetr A. Golovach, Pim van 't Hof and Daniël Paulusma
A preliminary version of this paper appeared in the proceedings of MFCS 2012, the 37th International Symposium on Mathematical Foundations of Computer Science (held on August 27-31, 2012 in Bratislava, Slovakia), Lecture Notes in Computer Science, vol. 7464, pp. 455-466, 2012.
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.