Non-crossing shortest paths lengths in planar graphs in linear time

DOI10.1016/J.DAM.2023.12.011OpenAlexW4390139760MaRDI QIDQ6153472FDOQ6153472

Authors Lorenzo Balzotti, Paolo G. Franciosa

Publication date 14 February 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2023.12.011

zbMATH Keywords

shortest pathsundirected planar graphsnon-crossing paths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Recommendations

• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Shortest non-crossing walks in the plane
• Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
• Multiple-source shortest paths in planar graphs
• Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm

Cites work

• A framework for solving VLSI graph layout problems
• A linear-time algorithm for a special case of disjoint set union
• Faster shortest-path algorithms for planar graphs
• How vulnerable is an undirected planar graph with respect to max flow
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight 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
• New lower bound techniques for VLSI
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time
• Non-crossing shortest paths lengths in planar graphs in linear time
• Preserving order in a forest in less than logarithmic time and linear space
• Shortest non-crossing walks in the plane
• Thick non-crossing paths and minimum-cost flows in polygonal domains
• k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON

Cited in

(1)

• How vulnerable is an undirected planar graph with respect to max flow

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

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