On the Edge Crossings of the Greedy Spanner
On the Edge Crossings of the Greedy Spanner
复制标题
贪婪扳手的边缘交叉
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Hadi Khodabandeh
中科院分区：
文献类型：
--
作者：
D. Eppstein;Hadi Khodabandeh
$t$-spanners 用于近似度量空间中一组点之间的成对距离。与对的总数相比，它们只有很少的边，并且它们提供任意两个任意点的距离的 $t$ 近似值。构建此类图的方法有很多种，就权重和结果图的边数而言，最有效的方法之一是贪婪扳手。在本文中，我们研究了欧几里德平面上点的贪婪扳手的边交叉。我们证明了具有较大边缘的交叉点数量的恒定上限，该上限仅取决于扳手的拉伸因子 $t$，并且我们表明可以存在超过有限数量的较小边缘的交叉点。我们的结果表明，平面上点的贪婪扳手具有大小为 $mathcal{O}(sqrt n)$ 的分隔符，它们的平面化具有线性大小，并且这些图的分隔符层次结构可以在线性时间内从它们的平面化构建。
$t$-spanners are used to approximate the pairwise distances between a set of points in a metric space. They have only a few edges compared to the total number of pairs and they provide a $t$-approximation on the distance of any two arbitrary points. There are many ways to construct such graphs and one of the most efficient ones, in terms of weight and the number of edges of the resulting graph, is the greedy spanner. In this paper, we study the edge crossings of the greedy spanner for points in the Euclidean plane. We prove a constant upper bound for the number of intersections with larger edges that only depends on the stretch factor of the spanner, $t$, and we show there can be more than a bounded number of intersections with smaller edges. Our results imply that greedy spanners for points in the plane have separators of size $mathcal{O}(sqrt n)$, that their planarizations have linear size, and that a separator hierarchy for these graphs can be constructed from their planarizations in linear time.