Skip to main content

Research Repository

Advanced Search

Obtaining planarity by contracting few edges

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

Authors

P. A. Golovach

P. van 't Hog



Contributors

Branislav Rovan
Editor

Vladimiro Sassone
Editor

Peter Widmayer
Editor

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.

Citation

Golovach, P. A., van 't Hog, P., & Paulusma, D. (2012). Obtaining planarity by contracting few edges. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical foundations of computer science 2012 : 37th international symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings (455-466). https://doi.org/10.1007/978-3-642-32589-2_41

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