Spanners for directed transmission graphs

DOI10.1137/16M1059692MaRDI QIDQ4581909zbMATH OpenOpenAlexWikidataFDO

Authors Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth

Publication date 21 August 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.07798

zbMATH Keywords

quadtreepannerreachability oracletransmission graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05)

Abstract: Let $Psubsetmathbb{R}^2$ be a planar $n$-point set such that each point $pinP$ has an associated radius $r_p>0$. The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that for any $p,qinP$, there is an edge from $p$ to $q$ if and only if $d(p,q)leq{r}_p$. Let $t>1$ be a constant. A $t$-spanner for $G$ is a subgraph $HsubseteqG$ with vertex set $P$ so that for any two vertices $p,qinP$, we have $d_H(p,q)leqt{d}_G(p,q)$, where $d_H$ and $d_G$ denote the shortest path distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n(logn+logPsi))$ time, where $Psi$ is the ratio of the largest and smallest radius of a point in $P$. Using more advanced data structures, we obtain a construction that runs in $O(nlo{g}^{5}n)$ time, independent of $Psi$. We give two applications for our spanners. First, we show how to use our spanner to find a BFS tree in $G$ from any given start vertex in $O(nlogn)$ time (in addition to the time it takes to build the spanner). Second, we show how to use our spanner to extend a reachability oracle to answer geometric reachability queries. In a geometric reachability query we ask whether a vertex $p$ in $G$ can "reach" a target $q$ which is an arbitrary point in the plane (rather than restricted to be another vertex $q$ of $G$ in a standard reachability query). Our spanner allows the reachability oracle to answer geometric reachability queries with an additive overhead of $O(lognlogPsi)$ to the query time and $O(nlogPsi)$ to the space.

Recommendations

• Spanners and Reachability Oracles for Directed Transmission Graphs
• Reachability oracles for directed transmission graphs
• Spanners for geometric intersection graphs with applications
• Spanners for Geometric Intersection Graphs
• Relaxed spanners for directed disk graphs

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs
• Compact oracles for reachability and approximate distances in planar digraphs
• Computational geometry. Algorithms and applications.
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Geometric Spanner Networks
• Geometric approximation algorithms
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
• Optimal Search in Planar Subdivisions
• Optimal halfspace range reporting in three dimensions
• Shortest paths in intersection graphs of unit disks
• Spanners and Reachability Oracles for Directed Transmission Graphs
• Spanners for geometric intersection graphs with applications
• Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent
• Unit disk graphs
• Voronoi Diagram in the Laguerre Geometry and Its Applications
• \(\pi /2\)-angle Xao graphs are spanners

Cited in

(12)

• Source-wise round-trip spanners
• Roundtrip spanners and roundtrip routing in directed graphs
• Dynamic connectivity in disk graphs
• Graph spanners
• Triangles and girth in disk graphs and transmission graphs
• Relaxed Spanners for Directed Disk Graphs
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• A note on reachability and distance oracles for transmission graphs
• Spanners and Reachability Oracles for Directed Transmission Graphs
• Reachability oracles for directed transmission graphs
• Reachability problems for transmission graphs
• Reachability problems for transmission graphs

This page was built for publication: Spanners for directed transmission graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581909)