TY - GEN

T1 - Fast minor testing in planar graphs

AU - Adler, Isolde

AU - Dorn, Frederic

AU - Fomin, Fedor V.

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

PY - 2010

Y1 - 2010

N2 - Minor containment is a fundamental problem in Algorithmic Graph Theory, as numerous graph algorithms use it as a subroutine. 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 Cu and Cv. 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 2 O(h)·n+O(n2· 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.

AB - Minor containment is a fundamental problem in Algorithmic Graph Theory, as numerous graph algorithms use it as a subroutine. 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 Cu and Cv. 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 2 O(h)·n+O(n2· 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.

KW - branchwidth

KW - dynamic programming

KW - graph minors

KW - parameterized complexity

KW - planar graphs

UR - http://www.scopus.com/inward/record.url?scp=78249287819&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78249287819&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15775-2_9

DO - 10.1007/978-3-642-15775-2_9

M3 - Conference contribution

AN - SCOPUS:78249287819

SN - 3642157742

SN - 9783642157745

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 97

EP - 109

BT - Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings

T2 - 18th Annual European Symposium on Algorithms, ESA 2010

Y2 - 6 September 2010 through 8 September 2010

ER -