Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

DOI10.1137/0216064zbMath0654.68087OpenAlexW2120424341MaRDI QIDQ3801095

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b8fa2dfb538111767547c1c79daee6f9efd3b9ce

zbMATH Keywords

minimum cut planar graphs data structures decision trees maximum flow multicommodity flow all pairs shortest paths heaps planar separator single source shortest paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Data structures (68P05)

Related Items

Computing connected-$k$-subgraph cover with connectivity requirement, Geometric dominating-set and set-cover via local-search, Unnamed Item, Fault-tolerant distance labeling for planar graphs, An efficient oracle for counting shortest paths in planar graphs, Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees, Call routing and the ratcatcher, Minimum Cuts in Surface Graphs, Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time, A simple linear algorithm for the edge-disjoint $(s, t)$-paths problem in undirected planar graphs, Balanced independent and dominating sets on colored interval graphs, How to catch marathon cheaters: new approximation algorithms for tracking paths, On the dilation spectrum of paths, cycles, and trees, The fastest itinerary in time-dependent decentralized travel information systems, Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, ON THE DISCRETE UNIT DISK COVER PROBLEM, A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs, A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes, Searching among intervals and compact routing tables, An efficient parallel algorithm for shortest paths in planar layered digraphs, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, On fast planning of suboptimal paths amidst polygonal obstacles in plane, Searching among intervals and compact routing tables, Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time, On temporal graph exploration, Algorithms for approximate shortest path queries on weighted polyhedral surfaces, Improved results on geometric hitting set problems, All-pairs-shortest-length on strongly chordal graphs, Two-level heaps: a new priority queue structure with applications to the single source shortest path problem, The planar multiterminal cut problem, An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, On the negative cost girth problem in planar networks, Sublinear separators, fragility and subexponential expansion, Optimal decremental connectivity in planar graphs, Local search is a PTAS for feedback vertex set in minor-free graphs, Unnamed Item, Faster shortest paths in dense distance graphs, with applications, Approximating the k-Level in Three-Dimensional Plane Arrangements, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Unnamed Item, Approximation algorithms for maximum independent set of pseudo-disks, A distributed shortest path algorithm for a planar network, Cycle bases in graphs characterization, algorithms, complexity, and applications, An efficient parallel algorithm for shortest paths in planar layered digraphs, A survey of geodesic paths on 3D surfaces, Counting and sampling minimum cuts in genus $g$ graphs, Splitting (complicated) surfaces is hard, Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures, Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem, AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER, Shortest path queries in digraphs of small treewidth, Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs, A framework for 1-D compaction with forbidden region avoidance, COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE, On the integral plane two-commodity flow problem, Dynamic algorithms for shortest paths in planar graphs, Shortest path computations in source-deplanarized graphs, I/O-efficient path traversal in succinct planar graphs, Improved approximation algorithms for box contact representations, Minimum vertex cover in ball graphs through local search, The within-strip discrete unit disk cover problem, Faster approximate diameter and distance oracles in planar graphs, Computing optimal shortcuts for networks, Shortest-path queries in static networks, Faster shortest-path algorithms for planar graphs, Planar graphs, negative weight edges, shortest paths, and near linear time, Single source shortest paths in $H$-minor free graphs, Unnamed Item, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, Subregion graph: a path planning acceleration structure for characters with various motion types in very large environments, Fault-tolerant distance labeling for planar graphs, Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack, An efficient oracle for counting shortest paths in planar graphs, Unnamed Item, On the Discrete Unit Disk Cover Problem, Capacitated discrete unit disk cover, Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees, Local search strikes again: PTAS for variants of geometric covering and packing, Single-source shortest paths and strong connectivity in dynamic planar graphs, Many distances in planar graphs, Reachability oracles for directed transmission graphs, Shortest path algorithms for nearly acyclic directed graphs, Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Fast and efficient solution of path algebra problems, Minimal connected enclosures on an embedded planar graph, Faster Approximate Diameter and Distance Oracles in Planar Graphs, Succinct and Implicit Data Structures for Computational Geometry, A linear-time algorithm for edge-disjoint paths in planar graphs, Non-crossing shortest paths in undirected unweighted planar graphs in linear time, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Electrical flows over spanning trees, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, A fast algorithm for maximum integral two-commodity flow in planar graphs, Optimally fast shortest path algorithms for some classes of graphs, An external memory data structure for shortest path queries, Short and Simple Cycle Separators in Planar Graphs, Flow in planar graphs with vertex capacities, Simple PTAS's for families of graphs excluding a minor