Shortest paths in directed planar graphs with negative lengths

2010/03/01 by Philip N. Klein, Shay Mozes, Oren Weimann · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Planar graph #Combinatorics #Directed graph #Planar #Mathematics #Directed acyclic graph #Feedback arc set #Node (physics) #Arc (geometry) #Graph #Discrete mathematics #Space (punctuation) #Computer science #Line graph #Geometry #Physics

paper · doi:10.1145/1721837.1721846

openalex publication_date 2010/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

We give an O ( n log 2 n )-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s , finds the distances from s to all nodes.

Citations

• Efficient Algorithms for Shortest Paths in Sparse Networks
• A Separator Theorem for Planar Graphs
• Finding small simple cycle separators for 2-connected planar graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Generalized Nested Dissection
• Faster Shortest-Path Algorithms for Planar Graphs

Cited by

• Planar separator theorem [wikipedia]