@inproceedings{fc79d2d09c31493a9099cf87910772ed,

title = "Contractions of planar graphs in polynomial time",

abstract = "We prove that for every graph H, there exists a polynomial-time algorithm deciding if a planar graph can be contracted to H. We introduce contractions and topological minors of embedded (plane) graphs and show that a plane graph H is an embedded contraction of a plane graph G, if and only if, the dual of H is an embedded topological minor of the dual of G. We show how to reduce finding embedded topological minors in plane graphs to solving an instance of the disjoint paths problem. Finally, we extend the result to graphs embeddable in an arbitrary surface.",

keywords = "contraction, dual graph, planar graph, topological minor",

author = "Marcin Kami{\'n}ski and Dani{\"e}l Paulusma and Thilikos, {Dimitrios M.}",

year = "2010",

doi = "10.1007/978-3-642-15775-2_11",

language = "English (US)",

isbn = "3642157742",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "122--133",

booktitle = "Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings",

edition = "PART 1",

note = "18th Annual European Symposium on Algorithms, ESA 2010 ; Conference date: 06-09-2010 Through 08-09-2010",

}