Non-crossing shortest paths in undirected unweighted planar graphs in linear time
type: Item
instance of: scholarly article
title: Non-crossing shortest paths in undirected unweighted planar graphs in linear time
DOI: 10.1007/978-3-031-09574-0_6
author: Lorenzo Balzotti
author: Paolo G. Franciosa
publication date: 2022-11-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/2102.10892
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7615732
zbMATH Keywords: planar graphs
zbMATH Keywords: non-crossing paths
zbMATH Keywords: shortest paths
zbMATH Keywords: undirected unweighted graphs
zbMATH Keywords: multiple pairs
zbMATH Keywords: external face
MaRDI profile type: Publication
OpenAlex ID: W4285207083
cites work: Max flow vitality in general and st‐planar graphs
cites work: Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
cites work: A framework for solving VLSI graph layout problems
cites work: Many distances in planar graphs
cites work: Shortest path queries in planar graphs
cites work: Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
cites work: Q5365044
cites work: Planar graphs, negative weight edges, shortest paths, and near linear time
cites work: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
cites work: Q4607915
cites work: Point-to-Point Shortest Path Algorithms with Preprocessing
cites work: An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
cites work: Faster shortest-path algorithms for planar graphs
cites work: Improved algorithms for min cut and max flow in undirected planar graphs
cites work: Multiple-source shortest paths in planar graphs
cites work: Short path queries in planar graphs in constant time
cites work: Finding a noncrossing Steiner forest in plane graphs under a 2-face condition
cites work: Q5743390
cites work: Improved Distance Queries in Planar Graphs
cites work: Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
cites work: Shortest Non-Crossing Rectilinear Paths in Plane Regions
cites work: A linear-time algorithm for edge-disjoint paths in planar graphs
description: scientific article; zbMATH DE number 7615732