Planar graphs, negative weight edges, shortest paths, and near linear time.

Jittat Fakcharoenphol Satish Rao

Published in: J. Comput. Syst. Sci. (2006)

Keyphrases

shortest path
planar graphs
weighted graph
edge weights
minimum weight
minimum length
road network
shortest path algorithm
undirected graph
minimum spanning tree
graph model
travel time
strongly connected components
graph partitioning
geodesic distance
worst case
bipartite graph
spanning tree
lower bound