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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904515
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

File

Minor-planar.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

766

Files downloads

109