Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.16
URN: urn:nbn:de:0030-drops-94796
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9479/
Chang, Hsien-Chih ; Gawrychowski, Pawel ; Mozes, Shay ; Weimann, Oren
Near-Optimal Distance Emulator for Planar Graphs
| pdf-format: |
|
Abstract
Given a graph G and a set of terminals T, a distance emulator of G is another graph H (not necessarily a subgraph of G) containing T, such that all the pairwise distances in G between vertices of T are preserved in H. An important open question is to find the smallest possible distance emulator. We prove that, given any subset of k terminals in an n-vertex undirected unweighted planar graph, we can construct in O~(n) time a distance emulator of size O~(min(k^2,sqrt{k * n})). This is optimal up to logarithmic factors. The existence of such distance emulator provides a straightforward framework to solve distance-related problems on planar graphs: Replace the input graph with the distance emulator, and apply whatever algorithm available to the resulting emulator. In particular, our result implies that, on any unweighted undirected planar graph, one can compute all-pairs shortest path distances among k terminals in O~(n) time when k=O(n^{1/3}).
BibTeX - Entry
@InProceedings{chang_et_al:LIPIcs:2018:9479,
author = {Hsien-Chih Chang and Pawel Gawrychowski and Shay Mozes and Oren Weimann},
title = {{Near-Optimal Distance Emulator for Planar Graphs}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {16:1--16:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9479},
URN = {urn:nbn:de:0030-drops-94796},
doi = {10.4230/LIPIcs.ESA.2018.16},
annote = {Keywords: planar graphs, shortest paths, metric compression, distance preservers, distance emulators, distance oracles}
}
| Keywords: | planar graphs, shortest paths, metric compression, distance preservers, distance emulators, distance oracles | |
| Seminar: | 26th Annual European Symposium on Algorithms (ESA 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 14.08.2018 |
