Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs. / Evald, Jacob; Fredslund-Hansen, Viktor; Wulff-Nilsen, Christian.
32nd International Symposium on Algorithms and Computation, ISAAC 2021. ed. / Hee-Kap Ahn; Kunihiko Sadakane. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. 23 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 212).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs
AU - Evald, Jacob
AU - Fredslund-Hansen, Viktor
AU - Wulff-Nilsen, Christian
N1 - Publisher Copyright: © Jacob Evald, Viktor Fredslund-Hansen, and Christian Wulff-Nilsen.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Color distance oracle
KW - Distance oracle
KW - Planar graph
KW - Vertex labels
UR - http://www.scopus.com/inward/record.url?scp=85122446530&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2021.23
DO - 10.4230/LIPIcs.ISAAC.2021.23
M3 - Article in proceedings
AN - SCOPUS:85122446530
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 32nd International Symposium on Algorithms and Computation, ISAAC 2021
A2 - Ahn, Hee-Kap
A2 - Sadakane, Kunihiko
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 32nd International Symposium on Algorithms and Computation, ISAAC 2021
Y2 - 6 December 2021 through 8 December 2021
ER -
ID: 291367568