Obtaining planarity by contracting few edges
Petr A. Golovach, Pim van 't Hof and Daniël Paulusma
Theoretical Computer Science, vol. 476, pp. 38-46, 2013.
[DOI][Preprint]
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.
[DOI]
Abstract:
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.