Fast minor testing in planar graphs
type: Item
instance of: scholarly article
title: Fast minor testing in planar graphs
zbMATH Open document ID: 1254.05185
author: Isolde Adler
author: Frederic Dorn
author: Fedor V. Fomin
author: Ignasi Sau
author: Dimitrios M. Thilikos
published in: Algorithmica
publication date: 2012-11-21T00:00:00Z
full work available at URL: Minor-planar.pdf
review text: For two graphs \(G\) and \(H\), the minor containment problem is to decide whether \(H\) is a minor of \(G\) (i.e. whether there are disjoint connected subgraphs of \(G\) corresponding to the vertices of \(H\) such that for each edge in \(H\) there is an edge in \(G\) between the corresponding subgraphs; such a set of subgraphs in \(G\) is called a model of \(H\)). This problem is NP-complete even in the case of planar graphs \(G\) and \(H\). The graph minor theory of Robertson and Seymour provides an \(f(h)n^3\) algorithm where \(h\) and \(n\) are the orders of \(H\) and \(G\), respectively. However, \(f(h)\) has a super-exponential growth. In this paper, for a planar graph \(G\), an \(\mathcal{O}(2^{\mathcal{O}(h)}n+n^2\log n)\) algorithm is presented. The authors assert that their algorithm ``is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs''. To prove the result, they introduce a novel approach of dynamic programming in planar graphs of bounded branch width (so-called partially embedded dynamic programming). Moreover, they are able to enumerate and count the number of models within the same time bound.
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 6109458
zbMATH Keywords: graph minors
zbMATH Keywords: planar graphs
zbMATH Keywords: branchwidth
zbMATH Keywords: parameterized complexity
zbMATH Keywords: dynamic programming
zbMATH Keywords: minor containment problem
zbMATH Keywords: model
zbMATH Keywords: algorithm
Wikidata QID: Q56235104
MaRDI profile type: Publication
OpenAlex ID: W1994533463
cites work: Faster Parameterized Algorithms for Minor Containment
cites work: Fast Minor Testing in Planar Graphs
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
cites work: Color-coding
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Treewidth lower bounds with brambles
cites work: Linearity of grid minors in treewidth with applications through bidimensionality
cites work: Bidimensionality: new connections between FPT algorithms and PTASs
cites work: Q5315023
cites work: Planar Subgraph Isomorphism Revisited
cites work: Subexponential parameterized algorithms
cites work: Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
cites work: On search, decision, and the efficiency of polynomial-time algorithms
cites work: Q4198056
cites work: Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
cites work: Improved bounds on the planar branchwidth with respect to the largest grid minor size
cites work: Branch decompositions and minor containment
cites work: Q4148000
cites work: Hadwiger's conjecture is decidable
cites work: A shorter proof of the graph minor algorithm: the unique linkage theorem
cites work: Q4535037
cites work: Applications of a Planar Separator Theorem
cites work: Graphs on surfaces
cites work: On random planar graphs, the number of planar graphs and their triangulations
cites work: Optimization and Recognition for K 5-minor Free Graphs in Linear Time
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Quickly excluding a planar graph
cites work: Graph minors. XX: Wagner's conjecture
cites work: Dynamic Programming for Graphs on Surfaces
cites work: On Hamilton cycles in certain planar graphs
cites work: Call routing and the ratcatcher
cites work: A Census of Planar Triangulations
DOI: 10.1007/S00453-011-9563-9
description: scientific article; zbMATH DE number 6109458