论文标题
在贪婪的扳手的边缘交叉口
On the Edge Crossings of the Greedy Spanner
论文作者
论文摘要
$ t $ spanners用于近似公制空间中一组点之间的成对距离。与成对的总数相比，它们只有几个边缘，并且在任意两个任意点的距离上提供了$ t $ Approximation。在重量方面，有很多方法可以构建此类图，并且是最有效的图形之一，而所产生图的边数是贪婪的跨度。在本文中，我们研究了贪婪的扳手的边缘交叉点在欧几里得平面中。我们证明了与仅取决于扳手的拉伸因子的交叉点的数量，这是一个常数的上限，并且我们显示的是有较小边缘的相交数量不仅仅是有界数的交叉点。我们的结果表明，飞机上的贪婪跨度具有尺寸$ \ 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.
