Obtaining Planarity by Contracting Few Edges
arXiv:1204.5113
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.
16 pages, 5 figures