A linear time algorithm for the induced disjoint paths problem in planar graphs

DOI10.1016/j.jcss.2011.10.004zbMath1241.05058OpenAlexW2020972784MaRDI QIDQ414938

Yusuke Kobayashi, Ken-ichi Kawarabayashi

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.10.004

zbMATH Keywords

induced subgraphlinear time algorithmplanar graphdisjoint paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Induced disjoint paths in circular-arc graphs in linear time, Graph editing to a fixed target, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Finding a shortest even hole in polynomial time, Combing a Linkage in an Annulus, The Induced Disjoint Paths Problem, Algorithms for finding an induced cycle in planar graphs, The (theta, wheel)-free graphs. IV: Induced paths and cycles, Induced disjoint paths problem in a planar digraph, Few induced disjoint paths for \(H\)-free graphs, Induced Disjoint Paths in Claw-Free Graphs, Induced disjoint paths in AT-free graphs, Few induced disjoint paths for \(H\)-free graphs, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Graph minors. XXII. Irrelevant vertices in linkage problems
• The strong perfect graph theorem
• Induced disjoint paths problem in a planar digraph
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. XI: Circuits on a surface
• Induced circuits in planar graphs
• Rooted routing in the plane
• The complexity of induced minors and related problems
• Graph minors. XIII: The disjoint paths problem
• Recognizing Berge graphs
• Maximal Flow Through a Network
• On the Computational Complexity of Combinatorial Problems
• Finding k Disjoint Paths in a Directed Planar Graph
• Non-interfering network flows