https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736769Adler, IsoldeIsoldeAdlerUiB - Department of Informatics [Bergen] - UiB - University of BergenDorn, FredericFredericDornUiB - Department of Informatics [Bergen] - UiB - University of BergenFomin, Fedor V.Fedor V.FominUiB - Department of Informatics [Bergen] - UiB - University of BergenSau Valls, IgnasiIgnasiSau VallsALGCO - Algorithmes, Graphes et Combinatoire - LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - UM - Université de Montpellier - CNRS - Centre National de la Recherche ScientifiqueThilikos, Dimitrios M.Dimitrios M.ThilikosDI NKUA - Department of Informatics and Telecomunications [Kapodistrian Univ] - NKUA - National and Kapodistrian University of AthensFast Minor Testing in Planar GraphsHAL CCSD2010Graph minorsPlanar graphsBranchwidthParameterized complexityDynamic programming[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Sau, Ignasi2019-09-16 11:16:182022-09-06 17:00:282019-09-16 11:17:04enConference papershttps://hal-lirmm.ccsd.cnrs.fr/lirmm-00736769/document10.1007/978-3-642-15775-2_9application/pdf1Minor 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 2O(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.