Fast Minor Testing in Planar Graphs |
| |
Authors: | Isolde Adler Frederic Dorn Fedor V. Fomin Ignasi Sau Dimitrios M. Thilikos |
| |
Affiliation: | 1. Institut f??r Informatik, Goethe-Universit?t, Frankfurt, Germany 2. Department of Informatics, University of Bergen, Bergen, Norway 3. AlGCo team, CNRS, LIRMM, Montpellier, France 4. Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece
|
| |
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 $mathcal{O}(2^{mathcal{O}(h)} cdot n +n^{2}cdotlog 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|