Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs
Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs
复制标题
通过在稀疏图中找到更多交叉来改进交叉引理
DOI：
--
复制
发表时间：
2006
影响因子：
0.8
通讯作者：
G. Tóth
中科院分区：
文献类型：
--
作者：
J. Pach;R. Radoicic;G. Tardos;G. Tóth
20年前，Ajtai等人和Leighton独立地发现，任何具有v个顶点和e > 4v条边的图的交叉数至少是ce 3/v2，其中c > 0是一个绝对常数。这个结果，被称为“交叉引理”，在离散和计算几何中有许多重要的应用。它紧到一个乘法常数。在这里，我们通过证明结果在c > 1024/31827 > 0.032时成立来改进常数的最佳已知值。这个证明有两个新的成分，它们本身就很有趣。我们证明了：（1）如果一个图能在平面上画成每条边至多与另外三条边相交，则它的边数不能超过5.5（v-2）;（2）任何图的交叉数至少为$frac 73 e-frac {25}3（v-2）。这两个边界都紧到一个加法常数（后者在范围$4vle ele 5v$）。
Twenty years ago, Ajtai et al. and, independently, Leighton discovered that the crossing number of any graph with v vertices and e > 4v edges is at least ce3/v2, where c > 0 is an absolute constant. This result, known as the "Crossing Lemma," has found many important applications in discrete and computational geometry. It is tight up to a multiplicative constant. Here we improve the best known value of the constant by showing that the result holds with c > 1024/31827 > 0.032. The proof has two new ingredients, interesting in their own right. We show that (1) if a graph can be drawn in the plane so that every edge crosses at most three others, then its number of edges cannot exceed 5.5(v-2); and (2) the crossing number of any graph is at least $frac73e-frac{25}3(v-2).$ Both bounds are tight up to an additive constant (the latter one in the range $4vle ele 5v$).