Fast minor testing in planar graphs (Q1759679)

For two graphs \(G\) and \(H\), the minor containment problem is to decide whether \(H\) is a minor of \(G\) (i.e. whether there are disjoint connected subgraphs of \(G\) corresponding to the vertices of \(H\) such that for each edge in \(H\) there is an edge in \(G\) between the corresponding subgraphs; such a set of subgraphs in \(G\) is called a model of \(H\)). This problem is NP-complete even in the case of planar graphs \(G\) and \(H\). The graph minor theory of Robertson and Seymour provides an \(f(h)n^3\) algorithm where \(h\) and \(n\) are the orders of \(H\) and \(G\), respectively. However, \(f(h)\) has a super-exponential growth. In this paper, for a planar graph \(G\), an \(\mathcal{O}(2^{\mathcal{O}(h)}n+n^2\log n)\) algorithm is presented. The authors assert that their algorithm ``is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs''. To prove the result, they introduce a novel approach of dynamic programming in planar graphs of bounded branch width (so-called partially embedded dynamic programming). Moreover, they are able to enumerate and count the number of models within the same time bound.