Irrelevant vertices for the planar disjoint paths problem

DOI10.1016/j.jctb.2016.10.001zbMath1350.05068arXiv1310.2378OpenAlexW2963908100WikidataQ57949601 ScholiaQ57949601MaRDI QIDQ345131

Daniel Lokshtanov, Dimitrios M. Thilikos, Isolde Adler, Philipp Klaus Krause, Stavros G. Kolliopoulos, Saket Saurabh

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.2378

zbMATH Keywords

treewidthgraph minorsdisjoint paths problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Combing a Linkage in an Annulus ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ Explicit linear kernels for packing problems ⋮ A lower bound on the tree-width of graphs with irrelevant vertices ⋮ Planar Digraphs ⋮ Parameterized complexity of set-restricted disjoint paths on chordal graphs ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Graph minors. XXI. graphs with unique linkages
• Graph minors. X: Obstructions to tree-decomposition
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• On the complexity of the disjoint paths problem
• A shorter proof of the graph minor algorithm
• Odd cycle packing
• Planar Disjoint-Paths Completion
• Domination Problems in Nowhere-Dense Classes
• Tight Bounds for Linkages in Planar Graphs
• The Induced Disjoint Paths Problem
• Faster Parameterized Algorithms for Minor Containment
• Induced Packing of Odd Cycles in a Planar Graph
• Finding k Disjoint Paths in a Directed Planar Graph
• Branch decompositions and minor containment
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth