Kaminski, M. and Paulusma, Daniel and Thilikos, D.M. (2011) 'Contracting planar graphs to contractions of triangulations.', Journal of discrete algorithms., 9 (3). pp. 299-306.
For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs C such that for every fixed H∈C, there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H. The class C is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H∈C if and only if there exists a constant cH such that if the treewidth of a graph is at least cH, it contains H as a contraction. We also provide a characterization of C in terms of minimal forbidden contractions.
|Keywords:||Planar graph, Dual graph, Contraction, Topological minor, Fixed parameter tractable.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1016/j.jda.2011.03.010|
|Record Created:||07 Dec 2011 14:35|
|Last Modified:||03 Apr 2013 16:19|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|