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
Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 14 novembre 2013 - 15:55:25
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral




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〉



Consultations de la notice