A linear-time algorithm for edge-disjoint paths in planar graphs

DOI10.1007/BF01294465zbMath0841.05086OpenAlexW2066881276MaRDI QIDQ1842575

Dorothea Wagner, Karsten Weihe

Publication date: 14 July 1996

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01294465

zbMATH Keywords

planar graphsedge-disjoint pathslinear-time algorithmevenness conditiontheorem of Okamura and Seymour

Mathematics Subject Classification ID

Paths and cycles (05C38) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Euclidean maximum matchings in the plane -- local to global ⋮ The order-interval hypergraph of a finite poset and the König property ⋮ A Combinatorial Algorithm for the Planar Multiflow Problem with Demands Located on Three Holes ⋮ Online interval scheduling with predictions ⋮ Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ On complexity, representation and approximation of integral multicommodity flows ⋮ An algorithm for node-capacitated ring routing ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms ⋮ A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works ⋮ Non-crossing shortest paths in undirected unweighted planar graphs in linear time

Cites Work

• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• A linear-time algorithm for a special case of disjoint set union
• Algorithms for routing in planar graphs
• Multicommodity flows in planar graphs
• Algorithms and computation. 4th international symposium, ISAAC '93, Hong Kong, December 15--17, 1993. Proceedings
• On multicommodity flows in planar graphs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Routing through a generalized switchbox
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Maximum Flow in Planar Networks
• Faster shortest-path algorithms for planar graphs

This page was built for publication: A linear-time algorithm for edge-disjoint paths in planar graphs