Conroy, Jonathan B. ;
Tóth, Csaba D.
HopSpanners for Geometric Intersection Graphs
Abstract
A tspanner of a graph G = (V,E) is a subgraph H = (V,E') that contains a uvpath of length at most t for every uv ∈ E. It is known that every nvertex graph admits a (2k1)spanner with O(n^{1+1/k}) edges for k ≥ 1. This bound is the best possible for 1 ≤ k ≤ 9 and is conjectured to be optimal due to Erdős' girth conjecture.
We study tspanners for t ∈ {2,3} for geometric intersection graphs in the plane. These spanners are also known as thop spanners to emphasize the use of graphtheoretic distances (as opposed to Euclidean distances between the geometric objects or their centers). We obtain the following results: (1) Every nvertex unit disk graph (UDG) admits a 2hop spanner with O(n) edges; improving upon the previous bound of O(nlog n). (2) The intersection graph of n axisaligned fat rectangles admits a 2hop spanner with O(nlog n) edges, and this bound is the best possible. (3) The intersection graph of n fat convex bodies in the plane admits a 3hop spanner with O(nlog n) edges. (4) The intersection graph of n axisaligned rectangles admits a 3hop spanner with O(nlog² n) edges.
BibTeX  Entry
@InProceedings{conroy_et_al:LIPIcs.SoCG.2022.30,
author = {Conroy, Jonathan B. and T\'{o}th, Csaba D.},
title = {{HopSpanners for Geometric Intersection Graphs}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {30:130:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16038},
URN = {urn:nbn:de:0030drops160381},
doi = {10.4230/LIPIcs.SoCG.2022.30},
annote = {Keywords: geometric intersection graph, unit disk graph, hopspanner}
}
01.06.2022
Keywords: 

geometric intersection graph, unit disk graph, hopspanner 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 