Skip to Main content Skip to Navigation
Journal articles

Fast Minor Testing in Planar Graphs

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 metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos <>
Submitted on : Monday, September 16, 2019 - 11:10:17 AM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Saturday, February 8, 2020 - 5:25:35 PM


Files produced by the author(s)




Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau Valls, 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