License: 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.2017.25
URN: urn:nbn:de:0030-drops-78382
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7838/
Go to the corresponding LIPIcs Volume Portal

Chan, Timothy M. ; Skrepetos, Dimitrios

Faster Approximate Diameter and Distance Oracles in Planar Graphs

pdf-format:
LIPIcs-ESA-2017-25.pdf (0.4 MB)

Abstract

We present an algorithm that computes a (1+varepsilon)-approximation of the diameter of a weighted, undirected planar graph of n vertices with non-negative edge lengths in O(nlog n(log n + (1/varepsilon)^5)) expected time, improving upon the O(n((1/varepsilon)^4 log^4(n) + 2^{O(1/varepsilon)}))-time algorithm of Weimann and Yuster [ICALP 2013]. Our algorithm makes two improvements over that result: first and foremost, it replaces the exponential dependency on 1/varepsilon with a polynomial one, by adapting and specializing Cabello's recent abstract-Voronoi-diagram-based technique [SODA 2017] for approximation purposes; second, it shaves off two logarithmic factors by choosing a better sequence of error parameters during recursion.

Moreover, using similar techniques, we improve the (1+varepsilon)-approximate distance oracle of Gu and Xu [ISAAC 2015] by first replacing the exponential dependency on 1/varepsilon on the preprocessing time and space with a polynomial one and second removing a logarithmic factor from the preprocessing time.

BibTeX - Entry

@InProceedings{chan_et_al:LIPIcs:2017:7838,
  author =	{Timothy M. Chan and Dimitrios Skrepetos},
  title =	{{Faster Approximate Diameter and Distance Oracles in Planar Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7838},
  URN =		{urn:nbn:de:0030-drops-78382},
  doi =		{10.4230/LIPIcs.ESA.2017.25},
  annote =	{Keywords: planar graphs, diameter, abstract Voronoi diagrams}
}

Keywords: planar graphs, diameter, abstract Voronoi diagrams
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI