Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Approximation Algorithms for k-Connected Graph Factors Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Efficient Vertex-Label Distance Oracles for Planar Graphs

Authors : Shay Mozes, Eyal E. Skop

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider distance queries in vertex labeled planar graphs. For any fixed \(0 < \epsilon \le 1/2\) we show how to preprocess an undirected planar graph with vertex labels and edge lengths to answer queries of the following form. Given a vertex u and a label \(\lambda \) return a \((1+\epsilon )\)-approximation of the distance between u and its closest vertex with label \(\lambda \). The query time of our data structure is \(O(\lg \lg {n} + \epsilon ^{-1})\), where n is the number of vertices. The space and preprocessing time of our data structure are nearly linear. We give a similar data structure for directed planar graphs with slightly worse performance. The best prior result for the undirected case has similar space and preprocessing bounds, but exponentially slower query time. No nontrivial results were previously considered for the directed case.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter On Temporally Connected Graphs of Small Cost
next chapter Constant-Time Local Computation Algorithms
Footnotes
1
Thorup’s treatment [11] of the undirected step does not contain the full details. See the full version of this paper for ellaboration.
 
2
The term quasi-\(\epsilon \)-cover is not used by Thorup. He uses \(\epsilon \)-covers for this notion.
 
3
Klein showed this lemma for \(\epsilon \)-covering sets, while Thorup showed a similar lemma using a different notion of \(\epsilon \)-covering sets.
 
4
In [11] a thinning procedure is given only for the directed case, and it is claimed that quasi-\(\epsilon \)-covering sets can be thinned. We believe this is not correct. See the full version. Instead, we give here a thinning procedure for \(\epsilon \)-covering sets.
 
5
We refer to the vertices of \(\mathcal T\) as nodes to distinguish them from the vertices of G.
 
6
These connections are only required for the efficient construction.
 
Literature
1.
Abraham, I., Chechik, S., Krauthgamer, R., Wieder, U.: Approximate nearest neighbor search in metrics of planar graphs. APPROX/RANDOM 2015, 20–42 (2015)
2.
Chechik, S.: Improved distance oracles and spanners for vertex-labeled graphs. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 325–336. Springer, Heidelberg (2012)CrossRef
3.
Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1), 3–23 (1997)MATHMathSciNetCrossRef
4.
Hermelin, D., Levy, A., Weimann, O., Yuster, R.: Distance oracles for vertex-labeled graphs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 490–501. Springer, Heidelberg (2011)CrossRef
5.
Kawarabayashi, K., Klein, P.N., Sommer, C.: Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 135–146. Springer, Heidelberg (2011)CrossRef
6.
Kawarabayashi, K., Sommer, C., Thorup, M.: More compact oracles for approximate distances in undirected planar graphs. In: SODA 2013, pp. 550–563 (2013)
7.
Klein, P.N.: Preprocessing an undirected planar network to enable fast approximate distance queries. In: SODA 2002, pp. 820–827 (2002)
8.
Li, M., Ma, C.C.C., Ning, L.: (1 + \(\epsilon \))-distance oracles for vertex-labeled planar graphs. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 42–51. Springer, Heidelberg (2013)CrossRef
9.
10.
Łącki, J., Ocwieja, J., Pilipczuk, M., Sankowski, P., Zych, A.: The power of dynamic distance oracles: efficient dynamic algorithms for the steiner tree. In: STOC 2015, pp. 11–20 (2015)
11.
Metadata
Title
Efficient Vertex-Label Distance Oracles for Planar Graphs
Authors
Shay Mozes
Eyal E. Skop
Copyright Year
2015
Book
Approximation and Online Algorithms

Print ISBN: 978-3-319-28683-9

Electronic ISBN: 978-3-319-28684-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-28684-6_9

Premium Partner

    Image Credits