A simple solution to the two paths problem in planar graphs

DOI10.1016/0020-0190(90)90071-5MaRDI QIDQ917331zbMATH OpenOpenAlexFDO

Authors Gerhard J. Woeginger

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(90)90071-5

zbMATH Keywords

graph algorithmsplanar graphsdisjoint pathstwo paths problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• Solving the 2-disjoint paths problem in nearly linear time
• STACS 2004
• A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
• A linear algorithms for the two paths problem on permutation graphs
• Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time

Cites work

• A Polynomial Solution to the Undirected Two Paths Problem
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• The directed subgraph homeomorphism problem

Cited in

(5)

• Rooted K₄-minors
• On the descriptive complexity of the two disjoint paths problem over undirected graphs
• A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
• Finding an Even Simple Path in a Directed Planar Graph
• Improved Algorithms for the 2-Vertex Disjoint Paths Problem

This page was built for publication: A simple solution to the two paths problem in planar graphs

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