Skip to main content

Research Repository

Advanced Search

Contractions of planar graphs in polynomial time

Kaminski, M.; Paulusma, D.; Thilikos, D.M.

Authors

M. Kaminski

D.M. Thilikos



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.

Citation

Kaminski, M., Paulusma, D., & Thilikos, D. (2010). Contractions of planar graphs in polynomial time. In Algorithms : ESA 2010 : 18th Annual European Symposium, 6-8 September 2010, Liverpool UK ; proceedings part I (122-133). https://doi.org/10.1007/978-3-642-15775-2_11

Conference Name The 18th Annual European Symposium
Publication Date Jan 1, 2010
Deposit Date Oct 6, 2010
Pages 122-133
Series Title Lecture notes in computer science
Series Number 6346
Series ISSN 0302-9743,1611-3349
Edition 18th
Book Title Algorithms : ESA 2010 : 18th Annual European Symposium, 6-8 September 2010, Liverpool UK ; proceedings part I.
DOI https://doi.org/10.1007/978-3-642-15775-2_11
Keywords Planar graph, Dual graph, Contraction, Topological minor.
Public URL https://durham-repository.worktribe.com/output/1159699