Disjoint Paths in a Planar Graph—A General Theorem

DOI10.1137/0405009MaRDI QIDQ3989016zbMATH OpenOpenAlexFDO

Authors Guoli Ding, Paul Seymour, Alexander Schrijver

Publication date 28 June 1992

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0405009

zbMATH Keywords

disjoint pathsplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Edge-disjoint paths in planar graphs
• scientific article; zbMATH DE number 4089593
• Length-bounded disjoint paths in planar graphs
• Disjoint paths in graphs. I: 3-planar graphs and basic obstructions
• Disjoint paths in graphs. (Reprint)
• On shortest disjoint paths in planar graphs
• On shortest disjoint paths in planar graphs
• Disjoint paths, planarizing cycles, and spanning walks
• Disjoint paths in graphs. II: A special case
• Disjoint paths in graphs

Cited in

(20)

• Edge-disjoint homotopic paths in a planar graph with one hole
• Disjoint paths in acyclic digraphs
• Disjoint paths in graphs. II: A special case
• Disjoint paths in graphs. III: Characterization
• Length-bounded disjoint paths in planar graphs
• Disjoint paths in graphs. (Reprint)
• Hardness of finding two edge-disjoint Min-Min paths in digraphs
• Multicriteria movement synchronization scheduling problems and algorithms
• Finding \(k\) partially disjoint paths in a directed planar graph
• Irrelevant vertices for the planar disjoint paths problem
• Necessary Condition for Path Partitioning Constraints
• scientific article; zbMATH DE number 508833 (Why is no real title available?)
• The pansophy of a graph
• Disjoint Paths in the Plane
• Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms
• On the connectivity of the disjointness graph of segments of point sets in general position in the plane
• Shortest two disjoint paths in conservative graphs
• Shortest two disjoint paths in conservative graphs
• An exponential time parameterized algorithm for planar disjoint paths
• Induced disjoint paths problem in a planar digraph

This page was built for publication: Disjoint Paths in a Planar Graph—A General Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3989016)