Fast Minor Testing in Planar Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2010

Fast Minor Testing in Planar Graphs

Abstract

Minor containment is a fundamental problem in Algorithmic Graph Theory, as numerous graph algorithms use it as a subroutine. 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 Cu and Cv. 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 2O(h)ċn+O(n2ċ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 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 partially embedded dynamic programming.
Fichier principal
Vignette du fichier
ark__67375_HCB-M3SJ9JPF-N.pdf (230.56 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive
Loading...

Dates and versions

lirmm-00736769 , version 1 (16-09-2019)

Identifiers

Cite

Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos. Fast Minor Testing in Planar Graphs. ESA 2010 - 18th Annual European Symposium on Algorithms, Sep 2010, Liverpool, United Kingdom. pp.97-109, ⟨10.1007/978-3-642-15775-2_9⟩. ⟨lirmm-00736769⟩
303 View
140 Download

Altmetric

Share

More