Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs

DOI10.1007/978-3-662-48350-3_20zbMath1465.68207arXiv1507.05980OpenAlexW1543313385MaRDI QIDQ3452786

Glencora Borradaile, Amir Nayyeri, Farzad Zafarani

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.05980

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Unnamed Item, Shortest Two Disjoint Paths in Polynomial Time, The Directed Disjoint Shortest Paths Problem

Cites Work

• Unnamed Item
• On shortest disjoint paths in planar graphs
• Matching is as easy as matrix inversion
• The directed subgraph homeomorphism problem
• Graph minors. XIII: The disjoint paths problem
• On the complexity of the disjoint paths problem
• A shorter proof of the graph minor algorithm
• Shortest vertex-disjoint two-face paths in planar graphs
• On the Computational Complexity of Combinatorial Problems
• Distributed algorithms for computing shortest pairs of disjoint paths
• Finding k Disjoint Paths in a Directed Planar Graph
• Shortest Two Disjoint Paths in Polynomial Time
• Faster shortest-path algorithms for planar graphs