Graph minors. VI. Disjoint paths across a disc

DOI10.1016/0095-8956(86)90031-6zbMath0598.05042OpenAlexW1982584550MaRDI QIDQ1079580

P. D. Seymour, Neil Robertson

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0095-8956(86)90031-6

zbMATH Keywords

planar graphspolynomial algorithmDISJOINT CONNECTING PATHS

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (33)

Improved self-reduction algorithms for graphs with bounded treewidth ⋮ Rooted routing in the plane ⋮ Grids and their minors ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Bandwidth, treewidth, separators, expansion, and universality ⋮ Bounded face-width forces \(K_7\)-minors in orientable surfaces ⋮ Graph minors. VIII: A Kuratowski theorem for general surfaces ⋮ On embedding graphs in trees ⋮ On completeness for NP via projection translations ⋮ Graph minors. VII: Disjoint paths on a surface ⋮ Subdivisions in planar graphs ⋮ Some recent progress and applications in graph minor theory ⋮ The disjoint shortest paths problem ⋮ Graph minors. XXII. Irrelevant vertices in linkage problems ⋮ The theory of guaranteed search on graphs ⋮ Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations ⋮ Graph minors. XIX: Well-quasi-ordering on a surface. ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Disjoint homotopic paths and trees in a planar graph ⋮ Directed circuits on a torus ⋮ On obstructions to small face covers in planar graphs ⋮ General vertex disjoint paths in series-parallel graphs ⋮ Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs ⋮ Unnamed Item ⋮ Constructing disjoint paths on expander graphs ⋮ Disjoint circuits of prescribed homotopies in a graph on a compact surface ⋮ A simple algorithm for multicuts in planar graphs with outer terminals ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Nested cycles in large triangulations and crossing-critical graphs ⋮ AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH ⋮ Disjoint Paths—A Survey ⋮ The structure of the models of decidable monadic theories of graphs ⋮ Minimal acyclic forbidden minors for the family of graphs with bounded path-width

Cites Work

• Graph minors. VII: Disjoint paths on a surface
• On the Computational Complexity of Combinatorial Problems

This page was built for publication: Graph minors. VI. Disjoint paths across a disc