All-pairs shortest paths in geometric intersection graphs

DOI10.1007/978-3-319-62127-2_22zbMath1417.68151OpenAlexW2725354306MaRDI QIDQ2405288

Dimitrios Skrepetos, Timothy M. Chan

Publication date: 22 September 2017

Full work available at URL: https://jocg.org/index.php/jocg/article/view/3068

zbMATH Keywords

disk graphsshortest pathsgeometric intersection graphsintersection searching data structures

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (3)

Near-optimal algorithms for shortest paths in weighted unit-disk graphs ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs.

This page was built for publication: All-pairs shortest paths in geometric intersection graphs