Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

Contractions of planar graphs in polynomial time.

Kaminski, M. and Paulusma, Daniel and Thilikos, D.M. (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. Berlin ; Heidelberg: Springer, pp. 122-133. Lecture notes in computer science. (6346).

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.

Item Type:Book chapter
Keywords:Planar graph, Dual graph, Contraction, Topological minor.
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1007/978-3-642-15775-2_11
Record Created:13 Oct 2010 14:50
Last Modified:03 Apr 2013 16:17

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library