Spanners for Directed Transmission Graphs

DOI10.1137/16M1059692zbMATH Open1398.68401arXiv1601.07798OpenAlexW3099199262WikidataQ129418690 ScholiaQ129418690MaRDI QIDQ4581909FDOQ4581909

Wolfgang Mulzer, Haim Kaplan, Paul Seiferth, Liam Roditty

Publication date: 21 August 2018

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

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.

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)

Cites Work

• Unit disk graphs
• Geometric Spanner Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Optimal Search in Planar Subdivisions
• Compact oracles for reachability and approximate distances in planar digraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
• Shortest paths in intersection graphs of unit disks
• Spanners for geometric intersection graphs with applications
• π/2-ANGLE YAO GRAPHS ARE SPANNERS
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• Voronoi Diagram in the Laguerre Geometry and Its Applications
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs
• Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent
• Spanners and Reachability Oracles for Directed Transmission Graphs

Cited In (12)

• Graph spanners
• Dynamic connectivity in disk graphs
• Source-wise round-trip spanners
• Relaxed Spanners for Directed Disk Graphs
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Reachability problems for transmission graphs
• Reachability problems for transmission graphs
• Roundtrip spanners and roundtrip routing in directed graphs
• Spanners and Reachability Oracles for Directed Transmission Graphs
• Title not available (Why is that?)
• Reachability oracles for directed transmission graphs
• Title not available (Why is that?)

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)