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.

## Abstract

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.

Item Type: | Article |
---|---|

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 |