A simple solution to the two paths problem in planar graphs

DOI10.1016/0020-0190(90)90071-5zbMATH Open0704.68091OpenAlexW2010031222MaRDI QIDQ917331FDOQ917331

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

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

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)

Cites Work

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

Cited In (5)

• Rooted \(K_4\)-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)