Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs

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

Documents

  • Fulltext

    Final published version, 1.15 MB, PDF document

Given an undirected n-vertex planar graph G = (V, E, ω) with non-negative edge weight function ω : E → R and given an assigned label to each vertex, a vertex-labeled distance oracle is a data structure which for any query consisting of a vertex u and a label λ reports the shortest path distance from u to the nearest vertex with label λ. We show that if there is a distance oracle for undirected n-vertex planar graphs with non-negative edge weights using s(n) space and with query time q(n), then there is a vertex-labeled distance oracle with Õ(s(n))1 space and Õ(q(n)) query time. Using the state-of-the-art distance oracle of Long and Pettie [12], our construction produces a vertex-labeled distance oracle using n1+o(1) space and query time Õ(1) at one extreme, Õ(n) space and no(1) query time at the other extreme, as well as such oracles for the full tradeoff between space and query time obtained in their paper. This is the first non-trivial exact vertex-labeled distance oracle for planar graphs and, to our knowledge, for any interesting graph class other than trees.

Original languageEnglish
Title of host publication32nd International Symposium on Algorithms and Computation, ISAAC 2021
EditorsHee-Kap Ahn, Kunihiko Sadakane
Number of pages14
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2021
Article number23
ISBN (Electronic)9783959772143
DOIs
Publication statusPublished - 2021
Event32nd International Symposium on Algorithms and Computation, ISAAC 2021 - Fukuoka, Japan
Duration: 6 Dec 20218 Dec 2021

Conference

Conference32nd International Symposium on Algorithms and Computation, ISAAC 2021
LandJapan
ByFukuoka
Periode06/12/202108/12/2021
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume212
ISSN1868-8969

Bibliographical note

Publisher Copyright:
© Jacob Evald, Viktor Fredslund-Hansen, and Christian Wulff-Nilsen.

    Research areas

  • Color distance oracle, Distance oracle, Planar graph, Vertex labels

ID: 291367568