Non-crossing shortest paths in undirected unweighted planar graphs in linear time
From MaRDI portal
Publication:2097216
DOI10.1007/978-3-031-09574-0_6OpenAlexW4285207083MaRDI QIDQ2097216
Lorenzo Balzotti, Paolo Giulio Franciosa
Publication date: 11 November 2022
Full work available at URL: https://arxiv.org/abs/2102.10892
planar graphsshortest pathsnon-crossing pathsexternal facemultiple pairsundirected unweighted graphs
Related Items (5)
Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ 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
- A framework for solving VLSI graph layout problems
- A linear-time algorithm for edge-disjoint paths in planar graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- 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
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
- Shortest Non-Crossing Rectilinear Paths in Plane Regions
- Improved Distance Queries in Planar Graphs
- Max flow vitality in general and st‐planar graphs
- 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
This page was built for publication: Non-crossing shortest paths in undirected unweighted planar graphs in linear time
