Fast Minor Testing in Planar Graphs

Isolde Adler 1 Frederic Dorn 1 Fedor Fomin 1 Ignasi Sau 2 Dimitrios M. Thilikos 3, 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 $\cO(2^{\mathcal{O}(h)} \cdot n + n^{2}\cdot \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 {\sl 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 \emph{partially embedded dynamic programming
Document type :
Journal articles
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download
Contributor : Dimitrios M. Thilikos <>
Submitted on : Monday, September 16, 2019 - 11:10:17 AM
Last modification on : Friday, November 1, 2019 - 11:46:02 AM


Files produced by the author(s)




Isolde Adler, Frederic Dorn, Fedor Fomin, Ignasi Sau, Dimitrios M. Thilikos. Fast Minor Testing in Planar Graphs. Algorithmica, Springer Verlag, 2012, 64 (1), pp.69-84. ⟨10.1007/s00453-011-9563-9⟩. ⟨lirmm-00904515⟩



Record views


Files downloads