## 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.

Original language | English (US) |
---|---|

Pages (from-to) | 299-306 |

Number of pages | 8 |

Journal | Journal of Discrete Algorithms |

Volume | 9 |

Issue number | 3 |

DOIs | |

State | Published - Sep 2011 |

## Keywords

- Contraction
- Dual graph
- Fixed parameter tractable
- Planar graph
- Topological minor

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics