Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time

DOI10.7155/jgaa.00610OpenAlexW4312541730MaRDI QIDQ5886044

Lorenzo Balzotti, Paolo Giulio Franciosa

Publication date: 30 March 2023

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00610

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Non-crossing shortest paths lengths in planar graphs in linear time ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ How vulnerable is an undirected planar graph with respect to max flow

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On shortest disjoint paths in planar graphs
• A framework for solving VLSI graph layout problems
• The disjoint shortest paths problem
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Shortest vertex-disjoint two-face paths in planar graphs
• Shortest path queries in planar graphs
• Short path queries in planar graphs in constant time
• An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• New lower bound techniques for VLSI
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Finding k Disjoint Paths in a Directed Planar Graph
• Shortest Non-Crossing Rectilinear Paths in Plane Regions
• k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
• The Directed Disjoint Shortest Paths Problem
• Improved Distance Queries in Planar Graphs
• Geometric k Shortest Paths
• Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
• Improved algorithms for min cut and max flow in undirected planar graphs
• Point-to-Point Shortest Path Algorithms with Preprocessing
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
• Faster shortest-path algorithms for planar graphs
• Many distances in planar graphs
• Finding a noncrossing Steiner forest in plane graphs under a 2-face condition