一种新的图交叉算法

去年10月，雅各布·霍姆(Jacob Holm)和伊娃·罗滕伯格(Eva Rotenberg)在翻阅几个月前发布的一篇论文时，意识到自己坐在了一个大东西上。

几十年来，计算机科学家一直在努力开发一种快速算法，用于确定何时可以向图形添加边，使其保持“平面”，即它的边不会相互交叉。但该领域一直无法改进20多年前发布的算法。

霍姆和罗滕伯格惊讶地发现，他们的论文包含了做得更好所需的洞察力。哥本哈根大学的计算机科学家霍尔姆说，它“解决了我们在实际获得真正的算法方面遇到的主要绊脚石之一”。“我们可能会把整件事都泄露出去。”

两人争先恐后地起草了一份新的文件。他们在6月份的ACM计算理论研讨会上展示了它，在那里他们详细介绍了一种检查图形是否为平面的指数级更好的方法。

路易斯大学的计算机科学家朱塞佩·意大利亚诺(Giuseppe Italiano)说：“新算法是一次非凡的巡回演出。”他也是1996年那篇描述目前第二快算法的论文的合著者之一。“当我与人合著那篇论文时，我没想到会出现这种情况。”

图是由边连接的节点的集合。它们可以用来代表从社会网络到道路系统再到电路板上的电气连接的一切。在电路板中，如果图形不是平面的，则意味着两条导线相互交叉并短路。

早在1913年，平面图就出现在一本名为“三效用问题”(Three-Utility Problem)的智力问答中，发表在“链”杂志(Strand Magazine)上。它要求读者在不跨越任何连接的情况下，将三所房子与三家公用事业公司-水、天然气和电力-连接起来。用不了多久就会发现这件事做不到。

但更复杂的图形是否为平面并不总是立竿见影的。而且，当你开始添加边时，就更难判断复杂的平面图是否保持平面，就像规划新的高速公路路段时一样。

计算机科学家一直在寻找一种算法，可以快速确定是否可以在保持图形平面化的同时进行所需的更改，并且当只有一小部分受到影响时，不需要检查图形的每一个单独部分。1996年的算法需要许多计算步骤，这些步骤大致与图中节点数量的平方根成正比。

霍尔姆说：“(这)比每次都从头开始做要好得多，但这并不是真的很好。”

新算法通过与图中节点数的对数的立方成正比的多个步骤来检查平面性-这是一个指数级的改进。霍尔姆和罗滕伯格是丹麦技术大学的计算机科学家，他们利用去年发现的平面图的一种特殊性质实现了加速。

要理解他们的方法，首先要注意的是，可以用多种方式绘制相同的平面图。在这些不同的图形中，连接保持不变，但边可能位于彼此相对的不同位置。

例如，通过将节点1、2和3形成的三角形翻转到连接节点2和3的边上，可以将图形A更改为图形B。图形B的顶部也可以反射到节点4和节点5上，以生成图形C。这些图形看起来不同，但它们是相同的图形。

现在假设您想要插入一条连接平面图中两个节点(例如下例中的节点1和6)的新边。要做到这一点，您需要执行一系列翻转动作。从左侧的起始位置开始，需要翻转两次才能将节点1移动到一个空间中，在该空间中，节点1可以连接到节点6，而无需跨越任何其他边。

在他们2019年的论文中，Holm和Rotenberg发现，一些图纸为插入边缘提供了比其他图纸更有利的开始位置。这些“好”的图画在不破坏平面性的情况下接受边缘只有几个翻转的距离。

他们在10月份迟迟才认识到的是，翻转让你更接近于能够添加新的边，也让图表更接近于他们已经识别的一幅好画。通过显示一系列翻转不可避免地将图形移向有利的绘图，新算法为您在找到插入边的方法之前可能需要执行的翻转次数提供了后盾(前提是插入完全可能)。

霍尔姆说：“我们很快意识到，有了这个新的分析，一个概念上非常、非常简单的算法就能解决这个问题。”

新算法一次执行一个翻转，寻找解决方案。最终，会发生两件事中的一件：要么算法找到插入所需边的方法，要么下一次翻转撤消上一次翻转-在这一点上，算法得出结论，没有办法添加边。

“我们称之为懒惰贪婪(算法)，”Rotenberg解释说。“它只进行适应边缘所需的更改。”

他们的新方法接近-但没有完全达到-这类问题的最佳算法(或下限)的性能。对于大多数真实世界的应用程序来说，新算法还必须经历太多的步骤，在这些应用程序中，相关的图形通常足够简单，可以用蛮力方法进行检查。

但对于霍姆和罗滕伯格来说，算法的速度不如加速它的洞察力重要。Rotenberg说：“从这种理解中产生了一些快速的东西。”

意大利人认为，它最终可能会对现实世界的应用程序有所帮助。他说：“(这很可能)迟早会对计算机科学和数学以外的领域产生影响。”

至于何时会出现更快的算法，没有人知道。这可能需要一个全新的突破，或者秘密成分可能已经在那里，在一堆旧的研究论文中等待着。