论文标题
非托管边缘之间的横梁
Crossings between non-homotopic edges
论文作者
论文摘要
如果可以在平面上绘制它的方式，以使得连接相同的顶点的两个边缘可以在不经过顶点的情况下连续转换，并且没有相同的方式可以将循环缩小到最终的vertex，否则我们将其称为Multigraph {\ em non-homotopic}。很容易看出，$ n> 1 $顶点上的非远程多人物可以任意有很多边缘。我们证明，对于某些常数$ c> 0 $，与$ n $顶点的非同时多式多数和$ m> 4n $边缘之间的交叉数大于$ c \ frac {m^2} {n} $，并且这种界限紧密地限制在polygogarithmic因子上。我们还表明，下边界并非渐近，因为$ n $是固定的，而$ m $倾向于无限。
We call a multigraph {\em non-homotopic} if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic multigraph on $n>1$ vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with $n$ vertices and $m>4n$ edges is larger than $c\frac{m^2}{n}$ for some constant $c>0$, and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as $n$ is fixed and $m$ tends to infinity.
