Non-crossing shortest paths in undirected unweighted planar graphs in linear time

DOI10.1007/978-3-031-09574-0_6MaRDI QIDQ2097216zbMATH OpenOpenAlexFDO

Authors Lorenzo Balzotti, Paolo G. Franciosa

Publication date 11 November 2022

Full work available at URL https://arxiv.org/abs/2102.10892

zbMATH Keywords

external facemultiple pairsnon-crossing pathsplanar graphsshortest pathsundirected unweighted graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A framework for solving VLSI graph layout problems
• A linear-time algorithm for edge-disjoint paths in planar graphs
• An O(n\log ^2 n) Algorithm for Maximum Flow in Undirected Planar Networks
• Better tradeoffs for exact distance oracles in planar graphs
• Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm
• Exact distance oracles for planar graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Faster shortest-path algorithms for planar graphs
• Finding a noncrossing Steiner forest in plane graphs under a 2-face condition
• Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs
• Improved distance queries in planar graphs
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
• Many distances in planar graphs
• Max flow vitality in general and st-planar graphs
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Multiple-source shortest paths in planar graphs
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Point-to-Point Shortest Path Algorithms with Preprocessing
• Short path queries in planar graphs in constant time
• Shortest Non-Crossing Rectilinear Paths in Plane Regions
• Shortest non-crossing walks in the plane
• Shortest path queries in planar graphs

Cited in

(6)

• 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
• Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm

This page was built for publication: Non-crossing shortest paths in undirected unweighted planar graphs in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097216)