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

DOI10.1016/J.DAM.2023.12.011MaRDI QIDQ6153472zbMATH OpenOpenAlexFDO

Authors Lorenzo Balzotti, Paolo G. Franciosa

Publication date 14 February 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

non-crossing pathsshortest pathsundirected planar graphs

Mathematics Subject Classification ID

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

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
• k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
• 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

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)