Obtaining planarity by contracting few edges
(2012)
Presentation / Conference Contribution
Golovach, P. A., van 't Hog, P., & Paulusma, D. (2012, December). 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.