## Abstract

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if {u,v} is an edge of H, then there is an edge of G between components C _{u} and C _{v} . A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time O(2 ^{O}(h) · n+n ^{2}·log n) a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming.

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

Pages (from-to) | 69-84 |

Number of pages | 16 |

Journal | Algorithmica |

Volume | 64 |

Issue number | 1 |

DOIs | |

State | Published - Sep 2012 |

## Keywords

- Branchwidth
- Dynamic programming
- Graph minors
- Parameterized complexity
- Planar graphs

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics