Kaplan, Haim ;
Klost, Katharina ;
Mulzer, Wolfgang ;
Roditty, Liam ;
Seiferth, Paul ;
Sharir, Micha
Triangles and Girth in Disk Graphs and Transmission Graphs
Abstract
Let S subset R^2 be a set of n sites, where each s in S has an associated radius r_s > 0. The disk graph D(S) is the undirected graph with vertex set S and an undirected edge between two sites s, t in S if and only if st <= r_s + r_t, i.e., if the disks with centers s and t and respective radii r_s and r_t intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph T(S) is the directed graph with vertex set S and a directed edge from a site s to a site t if and only if st <= r_s, i.e., if t lies in the disk with center s and radius r_s.
We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in D(S) and in T(S). These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in D(S) and in T(S) can be found in O(n log n) expected time, and that the (weighted) girth of D(S) can be found in O(n log n) expected time. For this, we develop new tools for batched range searching that may be of independent interest.
BibTeX  Entry
@InProceedings{kaplan_et_al:LIPIcs:2019:11185,
author = {Haim Kaplan and Katharina Klost and Wolfgang Mulzer and Liam Roditty and Paul Seiferth and Micha Sharir},
title = {{Triangles and Girth in Disk Graphs and Transmission Graphs}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {64:164:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11185},
URN = {urn:nbn:de:0030drops111859},
doi = {10.4230/LIPIcs.ESA.2019.64},
annote = {Keywords: disk graph, transmission graph, triangle, girth}
}
06.09.2019
Keywords: 

disk graph, transmission graph, triangle, girth 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 