Obtaining Planarity by Contracting Few Edges

Petr A. Golovach, Pim van 't Hof, Daniel Paulusma

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…