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

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

File

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

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

658

Files downloads

28