Fast minor testing in planar graphs

Isolde Adler; Frederic Dorn; Fedor V. Fomin; Ignasi Sau; Dimitrios M. Thilikos

doi:10.1007/978-3-642-15775-2_9

Fast minor testing in planar graphs

Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 C_u and C_v. 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 2 ^O(h)·n+O(n²· 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.

Original language	English (US)
Title of host publication	Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
Pages	97-109
Number of pages	13
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-15775-2_9
State	Published - 2010
Event	18th Annual European Symposium on Algorithms, ESA 2010 - Liverpool, United Kingdom Duration: Sep 6 2010 → Sep 8 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6346 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th Annual European Symposium on Algorithms, ESA 2010
Country/Territory	United Kingdom
City	Liverpool
Period	9/6/10 → 9/8/10

Keywords

branchwidth
dynamic programming
graph minors
parameterized complexity
planar graphs

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-15775-2_9

Cite this

Adler, I., Dorn, F., Fomin, F. V., Sau, I., & Thilikos, D. M. (2010). Fast minor testing in planar graphs. In Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings (PART 1 ed., pp. 97-109). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6346 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-15775-2_9

Fast minor testing in planar graphs. / Adler, Isolde; Dorn, Frederic; Fomin, Fedor V. et al.
Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings. PART 1. ed. 2010. p. 97-109 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6346 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Adler, I, Dorn, F, Fomin, FV, Sau, I & Thilikos, DM 2010, Fast minor testing in planar graphs. in Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6346 LNCS, pp. 97-109, 18th Annual European Symposium on Algorithms, ESA 2010, Liverpool, United Kingdom, 9/6/10. https://doi.org/10.1007/978-3-642-15775-2_9

@inproceedings{d8b681d5c89d43c2883983a841753081,

title = "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 2 O(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.",

keywords = "branchwidth, dynamic programming, graph minors, parameterized complexity, planar graphs",

author = "Isolde Adler and Frederic Dorn and Fomin, {Fedor V.} and Ignasi Sau and Thilikos, {Dimitrios M.}",

year = "2010",

doi = "10.1007/978-3-642-15775-2_9",

language = "English (US)",

isbn = "3642157742",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "97--109",

booktitle = "Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings",

edition = "PART 1",

note = "18th Annual European Symposium on Algorithms, ESA 2010 ; Conference date: 06-09-2010 Through 08-09-2010",

}

TY - GEN

T1 - Fast minor testing in planar graphs

AU - Adler, Isolde

AU - Dorn, Frederic

AU - Fomin, Fedor V.

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

PY - 2010

Y1 - 2010

N2 - 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 2 O(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.

AB - 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 2 O(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.

KW - branchwidth

KW - dynamic programming

KW - graph minors

KW - parameterized complexity

KW - planar graphs

UR - http://www.scopus.com/inward/record.url?scp=78249287819&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78249287819&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15775-2_9

DO - 10.1007/978-3-642-15775-2_9

M3 - Conference contribution

AN - SCOPUS:78249287819

SN - 3642157742

SN - 9783642157745

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 97

EP - 109

BT - Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings

T2 - 18th Annual European Symposium on Algorithms, ESA 2010

Y2 - 6 September 2010 through 8 September 2010

ER -

Fast minor testing in planar graphs

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this