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

DOI10.1016/j.dam.2023.12.011OpenAlexW4390139760MaRDI QIDQ6153472

Lorenzo Balzotti, Paolo Giulio 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)

Related Items (1)

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

Cites Work

• A framework for solving VLSI graph layout problems
• A linear-time algorithm for a special case of disjoint set union
• Preserving order in a forest in less than logarithmic time and linear space
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time
• Thick non-crossing paths and minimum-cost flows in polygonal domains
• New lower bound techniques for VLSI
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
• Max flow vitality in general and st‐planar graphs
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Faster shortest-path algorithms for planar graphs
• Non-crossing shortest paths lengths in planar graphs in linear time
• How vulnerable is an undirected planar graph with respect to max flow
• Unnamed Item
• Unnamed Item

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