A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


  • Fulltext

    Accepted author manuscript, 535 KB, PDF document

Given an n-vertex planar embedded digraph G with non-negative edge weights and a face f of G, Klein presented a data structure with O(nlogn) space and preprocessing time which can answer any query (u,v) for the shortest path distance in G from u to v or from v to u in O(logn) time, provided u is on f. This data structure is a key tool in a number of state-of-the-art algorithms and data structures for planar graphs.
Klein's data structure relies on dynamic trees and the persistence technique as well as a highly non-trivial interaction between primal shortest path trees and their duals. The construction of our data structure follows a completely different and in our opinion very simple divide-and-conquer approach that solely relies on Single-Source Shortest Path computations and contractions in the primal graph. Our space and preprocessing time bound is O(nlog|f|) and query time is O(log|f|) which is an improvement over Klein's data structure when f has small size.
Original languageEnglish
Title of host publicationProceedings, Symposium on Simplicity in Algorithms (SOSA)
Publication date2022
Publication statusPublished - 2022
EventFifth SIAM Symposium on Simplicity of Algorithms (SOSA 2022) - Virtual
Duration: 10 Jan 202211 Jan 2022


ConferenceFifth SIAM Symposium on Simplicity of Algorithms (SOSA 2022)

Number of downloads are based on statistics from Google Scholar and www.ku.dk

No data available

ID: 300443460