Which Crossing Number Is It Anyway?
Which Crossing Number Is It Anyway?
复制标题
到底是哪个路口号码？
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Jj Anos Pach
中科院分区：
文献类型：
--
作者：
Jj Anos Pach
图G的绘制是一种映射，它为每个顶点分配平面上的一个点，并为每个边分配一个连接相应两点的简单连续圆弧。图G的交叉数是图G的最小交叉点个数。我们定义了两个新参数，如下所示。两两交叉数(分别为G的奇数)是交叉的边对的最小数目(分别为。奇数次)。我们证明了每个参数的确定都是一个NP-完全问题。我们还证明了其中最大的数(交叉数)不能超过最小的数(奇交数)的平方。我们的证明是基于Hanani的一个旧结果的推广，该结果具有独立意义。设G是一个图，E0是它的边的一个子集，使得有一个图G，其中属于E0的每条边与任何其他边相交偶数次。然后，可以重新绘制G，使得E_0的元素不涉及任何交叉。
A drawing of a graph G is a mapping which assigns to each vertex a point of the plane and to each edge a simple continuous arc connecting the corresponding two points. The crossing number of G is the minimum number of crossing points in any drawing of G. We deene two new parameters, as follows. The pairwise crossing number (resp. the odd-crossing number) of G is the minimum number of pairs of edges that cross (resp. cross an odd number of times) over all drawings of G. We prove that the determination of each of these parameters is an NP-complete problem. We also prove that the largest of these numbers (the crossing number) cannot exceed twice the square of the smallest (the odd-crossing number). Our proof is based on the following generalization of an old result of Hanani, which is of independent interest. Let G be a graph and let E 0 be a subset of its edges such that there is a drawing of G, in which every edge belonging E 0 crosses any other edge an even number of times. Then G can be redrawn so that the elements of E 0 are not involved in any crossing.