Sparse hop spanners for unit disk graphs
Sparse hop spanners for unit disk graphs
复制标题
单位圆盘图的稀疏跳扳手
DOI：
10.1016/j.comgeo.2021.101808
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tóth, Csaba D.
中科院分区：
文献类型：
--
作者：
Dumitrescu, Adrian;Ghosh, Anirban;Tóth, Csaba D.
平面上给定的点集 P 上的单位圆盘图 G 是一个几何图，其中两点 p, q∈ P 之间存在一条边当且仅当 | p q|≤ 1。 G 的生成子图 G′ 是 k 跳生成器当且仅当对于每条边 p q ∈ G，G′ 中的 p、q 之间存在一条最多有 k 个边的路径。对于平面上的单位圆盘图，我们得到以下结果。 (i) 每个 n 顶点单位圆盘图都有一个最多有 5.5n 条边的 5 跳扳手。我们分析了 Biniaz (2020) 构造的扳手家族，并将边数上限从 9n 改进到 5.5n。(ii) 使用新的构造，我们表明每个 n 顶点单位圆盘图都有一个最多有 11n 条边的 3 跳扳手。(iii) 每个 n 顶点单位圆盘图都有一个带有 O (n log n) 条边的 2 跳扳手。这是 2 跳扳手的第一个重要构造。(iv) 对于每个足够大的正整数 n，在圆上存在一个由 n 个点组成的集合 P，使得 P 上的每个平面跳扳手的跳拉伸因子至少为 4。以前，不知道大于 2 的下界。(v) 对于圆上的每个有限点集，存在一个平面（即无交叉）4 跳扳手。因此，这为圆上的点提供了严格的界限。 (vi) 对于任何正整数 k，k 跳扳手的最大次数不能从上面通过 k 的函数来界定。
A unit disk graph G on a given set P of points in the plane is a geometric graph where an edge exists between two points p, q∈ P if and only if| p q|≤ 1. A spanning subgraph G′ of G is a k-hop spanner if and only if for every edge p q∈ G, there is a path between p, q in G′ with at most k edges. We obtain the following results for unit disk graphs in the plane.(i) Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n.(ii) Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges.(iii) Every n-vertex unit disk graph has a 2-hop spanner with O (n log n) edges. This is the first nontrivial construction of 2-hop spanners.(iv) For every sufficiently large positive integer n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. Previously, no lower bound greater than 2 was known.(v) For every finite point set on a circle, there exists a plane (ie, crossing-free) 4-hop spanner. As such, this provides a tight bound for points on a circle.(vi) The maximum degree of k-hop spanners cannot be bounded from above by a function of k for any positive integer k.