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 metadatas

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


Files produced by the author(s)




Isolde Adler, Frederic Dorn, Fedor 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