论文标题
随机排列中边缘交叉方差的快速计算
Fast calculation of the variance of edge crossings in random arrangements
论文作者
论文摘要
图形$ g $，$ \ mathrm {cr}（g）$的交叉数是当在某个表面上绘制图形时产生的边缘交叉数的最小数量。确定$ \ mathrm {cr}（g）$在图理论中非常重要的问题。它的最大变体，即最大交叉数，$ \ mathrm {max-cr}（g）$，正在受到越来越多的关注。当我们考虑到边缘数量的差异时，当在某个空间中随机嵌入任意图的顶点时，我们考虑了边缘交叉数量的差异。在他的开创性研究中，月亮在完整的单分和二分图的随机线性布置方面得出了这一差异。鉴于需要有效的算法支持这类研究，并给予了空间网络中边缘交叉数量的日益增长的兴趣，在某个空间中顶点嵌入了顶点的网络，在这里，我们得出了一种算法，以在时间$ o（nm^2）中计算出任意图中的差异，该算法是$ o（nm^2），我们转变为一个在时间$ o（nms $ o（nm）中运行的差异。我们还为时间$ o（n）$的森林提供了一个。这些算法在广泛的随机布局（不仅在月球上）起作用，并且基于新型算术表达式，用于计算我们从以前的理论工作中发展的方差。这为许多依靠快速但精确计算的应用程序铺平了道路。
The crossing number of a graph $G$, $\mathrm{cr}(G)$, is the minimum number of edge crossings arising when drawing a graph on a certain surface. Determining $\mathrm{cr}(G)$ is a problem of great importance in Graph Theory. Its maximum variant, i.e. the maximum crossing number, $\mathrm{max-cr}(G)$, is receiving growing attention. Instead of an optimization problem on the number of crossings, here we consider the variance of the number of edge crossings, when embedding the vertices of an arbitrary graph uniformly at random in some space. In his pioneering research, Moon derived this variance on random linear arrangements of complete unipartite and bipartite graphs. Given the need of efficient algorithms to support this sort of research and given also the growing interest of the number of edge crossings in spatial networks, networks where vertices are embedded in some space, here we derive an algorithm to calculate the variance in arbitrary graphs in time $o(nm^2)$ that we transform into one that runs in time $O(nm)$ by reusing computations. We also derive one for forests that runs in time $O(n)$. These algorithms work on a wide range of random layouts (not only on Moon's) and are based on novel arithmetic expressions for the calculation of the variance that we develop from previous theoretical work. This paves the way for many applications that rely on a fast but exact calculation of the variance.
