Obtaining planarity by contracting few edges

Golovach, P. A.; van 't Hog, P.; Paulusma, D.

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.

• Presentation Conference Type: Conference Paper (Published)
• Publication Date: 2012
• Deposit Date: Mar 11, 2013
• Pages: 455-466
• Series Title: Lecture notes in computer science
• Series Number: 7464
• Series ISSN: 0302-9743,1611-3349
• Book Title: Mathematical foundations of computer science 2012 : 37th international symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings.
• ISBN: 9783642325885
• DOI: https://doi.org/10.1007/978-3-642-32589-2_41
• Keywords: Planar graphs, Edge contractions, FPT algorithms.
• Public URL: https://durham-repository.worktribe.com/output/1157379
• Additional Information: Series: (LNCS)Lecture Notes in Computer Science, Volume 7464 2012