论文标题
关键图的交叉数量的改进
Improvement on the crossing number of crossing-critical graphs
论文作者
论文摘要
图$ g $的交叉数是飞机上$ g $的所有图纸上的边缘交叉数的最小数量。如果其交叉数量至少为$ k $，则图$ g $是$ k $ - 交叉 - 关键点，但是如果我们删除$ g $的任何边缘，其交叉数量下降到$ k $以下。 $ k $ - 交叉 - 关键图的示例没有恰好的$ k $交叉点。里奇特（Richter）和托马森（Thomassen）在1993年证明，如果$ g $是$ k $ - 杂交，那么其交叉数量最多为$ 2.5k+16美元。我们将其改进为$ 2K+6 \ sqrt {k}+44 $。
The crossing number of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. A graph $G$ is $k$-crossing-critical if its crossing number is at least $k$, but if we remove any edge of $G$, its crossing number drops below $k$. There are examples of $k$-crossing-critical graphs that do not have drawings with exactly $k$ crossings. Richter and Thomassen proved in 1993 that if $G$ is $k$-crossing-critical, then its crossing number is at most $2.5k+16$. We improve this bound to $2k+6\sqrt{k}+44$.
