Fast Minor Testing in Planar Graphs

Abstract : 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 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736769
Contributor : Ignasi Sau <>
Submitted on : Monday, September 16, 2019 - 11:16:18 AM
Last modification on : Tuesday, January 14, 2020 - 1:36:09 PM

File

ark__67375_HCB-M3SJ9JPF-N.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau Valls, Dimitrios M. Thilikos. Fast Minor Testing in Planar Graphs. ESA: European Symposium on Algorithms, Sep 2010, Liverpool, United Kingdom. pp.97-109, ⟨10.1007/978-3-642-15775-2_9⟩. ⟨lirmm-00736769⟩

Share

Metrics

Record views

178

Files downloads

17