Kaplan, Haim ;
Mulzer, Wolfgang ;
Roditty, Liam ;
Seiferth, Paul
Spanners and Reachability Oracles for Directed Transmission Graphs
Abstract
Let P be a set of n points in d dimensions, each with an associated radius r_p > 0. The transmission graph G for P has vertex set P and an edge from p to q if and only if q lies in the ball with radius r_p around p. Let t > 1. A tspanner H for G is a sparse subgraph of G such that for any two vertices p, q connected by a path of length l in G, there is a pqpath of length at most tl in H. We show how to compute a tspanner for G if d=2. The running time is O(n (log n + log Psi)), where Psi is the ratio of the largest and smallest radius of two points in P. We extend this construction to be independent of Psi at the expense of a polylogarithmic overhead in the running time. As a first application, we prove a property of the tspanner that allows us to find a BFS tree in G for any given start vertex s of P in the same time.
After that, we deal with reachability oracles for G. These are data structures that answer reachability queries: given two vertices, is there a directed path between them? The quality of a reachability oracle is measured by the space S(n), the query time Q(n), and the preproccesing time. For d=1, we show how to compute an oracle with Q(n) = O(1) and S(n) = O(n) in time O(n log n). For d=2, the radius ratio Psi again turns out to be an important measure for the complexity of the problem. We present three different data structures whose quality depends on Psi: (i) if Psi < sqrt(3), we achieve Q(n) = O(1) with S(n) = O(n) and preproccesing time O(n log n); (ii) if Psi >= sqrt(3), we get Q(n) = O(Psi^3 sqrt(n)) and S(n) = O(Psi^5 n^(3/2)); and (iii) if Psi is polynomially bounded in n, we use probabilistic methods to obtain an oracle with Q(n) = O(n^(2/3)log n) and S(n) = O(n^(5/3) log n) that answers queries correctly with high probability. We employ our tspanner to achieve a fast preproccesing time of O(Psi^5 n^(3/2)) and O(n^(5/3) log^2 n) in case (ii) and (iii), respectively.
BibTeX  Entry
@InProceedings{kaplan_et_al:LIPIcs:2015:5106,
author = {Haim Kaplan and Wolfgang Mulzer and Liam Roditty and Paul Seiferth},
title = {{Spanners and Reachability Oracles for Directed Transmission Graphs}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {156170},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5106},
URN = {urn:nbn:de:0030drops51062},
doi = {10.4230/LIPIcs.SOCG.2015.156},
annote = {Keywords: Transmission Graphs, Reachability Oracles, Spanner, Intersection Graph}
}
2015
Keywords: 

Transmission Graphs, Reachability Oracles, Spanner, Intersection Graph 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

2015 