Approximating the rectilinear crossing number
Approximating the rectilinear crossing number
复制标题
近似直线交叉数
DOI：
10.1016/j.comgeo.2019.04.003
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Suk, Andrew
中科院分区：
文献类型：
--
作者：
Fox, Jacob;Pach, János;Suk, Andrew
图的直线绘制是一种映射，它为每个顶点分配平面上的一个点，为每条边分配一条连接相应两点的直线段。图的直线交叉数是 G 的任何直线图中交叉边对的最小数量。确定或估计似乎是一个难题，而确定是否是已知的 NP 困难问题。事实上， 的渐近行为仍然未知。在本文中，我们提出了一种确定性时间算法，该算法可以找到具有交叉边对的任意顶点图 G 的直线图。与 Ajtai 等人提出的著名的交叉引理一起。 和 Leighton，这个结果意味着对于任何密集顶点图 G，我们可以有效地找到具有成对交叉边的 G 的直线图。
Astraight-linedrawing of a graphGis a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. Therectilinear crossing numberof a graph, is the minimum number of pairs of crossing edges in any straight-line drawing ofG. Determining or estimatingappears to be a difficult problem, and deciding ifis known to be NP-hard. In fact, the asymptotic behavior ofis still unknown.In this paper, we present a deterministic-time algorithm that finds a straight-line drawing of anyn-vertex graphGwithpairs of crossing edges. Together with the well-known Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any densen-vertex graphG, one can efficiently find a straight-line drawing ofGwithpairs of crossing edges.