两位计算机科学家在一个意想不到的地方发现了一个想法，这对他们在图论上的突破很有用
2019年10月，雅各布·霍尔姆（Jacob Holm）和伊娃·罗滕伯格（Eva Rotenberg）翻阅了几个月前发表的作品-突然意识到他们偶然发现了一件严肃的事情。
数十年来，计算机科学家一直在尝试设计一种快速算法，以确定是否可以将边缘添加到特定图形中，以使其保持“平面”，也就是说，其边缘不相交。但是，没有人成功地改进了20年前发布的算法。
Holm和Rothenberg惊讶地发现他们的工作有一种想法可以使该算法得到极大的改进。哥本哈根大学的计算机科学家霍尔姆说：“她“找出了真正算法的主要障碍之一”。 “也许我们已经完全披露了这个问题。”
这对夫妇赶忙撰写新文章。他们在6月的美国计算机协会计算理论研讨会上提出了该方法，他们详细介绍了一种检查图形平面度的方法，该方法比以前的方法指数级地提高。
“新算法真正精湛，”路易斯大学的计算机科学家Giuseppe Italiano说，他是1996年论文的合著者，该论文现在描述了第二快的算法。 “当我参与该作品的写作时，我认为这不可能发生。”
图是由边连接的顶点的集合。它们可用于标记从社交网络到道路网络和电路板上电导体的所有内容。如果在后一种情况下图形不是平面的，则两条导体将彼此交叉，这将导致短路。
早在1913年，平面图就出现在有关“三栋房屋”的复杂“公共”难题中，该难题已在The Strand Magazine上发表。该出版物要求读者为三所房屋进行通讯，将它们各自与三个能源载体（水，天然气和电力）连接，以使通讯不会相互交叉。很快就会意识到这项任务是无法克服的。
但是，在图形更复杂的情况下，它们是否为平面并不总是很明显。当您开始向其添加边线时，很难判断复杂的图形是否会保持平面状-就像规划新道路时一样。
长期以来，计算机科学家一直在寻找一种算法，该算法可以快速确定是否可以进行所需的更改，以使图形保持平面，而仅在图形的一小部分发生更改时，无需遍历图形的每个部分。为此，1996年算法需要执行多个步骤，大致与图中顶点数的平方根成比例。
霍尔姆说：“这比每次从头开始检查所有内容要好得多，但并不完美。”
新算法按与图形中顶点数量的对数的立方成比例的步数检查平面度-改进是指数级的。丹麦技术大学的Holm和Rothenberg通过利用他们去年发现的平面图的特殊特性，实现了这种加速。
要了解他们的方法，您必须首先注意可以以不同的方式绘制相同的平面图。这些选项的所有连接均保持不变，但是可以以不同的方式将边缘相对放置。
例如，通过相对于连接顶点2和3的边翻转构成顶点1,2和3的三角形，可以将图A更改为图B。图B的顶部也可以相对于顶点4和5翻转，得到图C。不同，但表示相同的图。
现在，假设您要插入一个连接平面图的两个顶点（例如，顶点1和6）的新边。为此，您需要运行一系列翻转。从左侧的起始位置开始，可以进行两次翻转，将顶点1转移到可以与顶点6连接的位置，而无需交叉其他边缘。
Holm和Rothenberg在2019年的论文中发现，某些图形在边缘插入方面比其他图形更具优势。这些“良好”图案只需翻转几下即可添加新边缘，而不会破坏平面度。
他们在十月的最后实现是，翻转使您更接近可以添加新边的位置，也使图形更接近他们已经定义的良好模式之一。通过显示一系列翻转不可避免地使图形更接近于首选模式，可以制定一种新算法来限制翻转次数，您可能需要找到一种添加边的方法（如果可能的话）。
“我们很快意识到，通过这种新的分析可以解决问题
Holm说：“这种算法在概念上非常简单。”
Jacob Holm和Eva Rothenberg
新算法一次执行一次翻转以找到解决方案。结果，发生了两件事之一：算法找到了一种插入所需边缘的方法，或者下一次翻转取消了前一个边缘-之后，该算法得出结论，无法添加新边缘。
“我们称这种算法为懒惰贪婪，” Rotenberg解释说。 “它只是进行必要的更改以适应新的肋骨。”
他们的新方法近似（但不匹配）用于此类任务的最佳算法的性能。新算法还必须经过太多步骤，才能在大多数实际应用中使用-通常，图形足够简单，可以进行暴力测试。
但是对于Holm和Rothenberg来说，算法的速度并不像加速算法的思想那么重要。罗滕伯格说：“这种理解会立即产生后果。”
Italiano相信它将最终找到真正的用途。他说：“迟早，它肯定会影响计算机科学以外的数学领域。”
没有人知道何时会出现更快的算法。这可能需要一个全新的突破，或者秘密成分可能已经存在于某个地方，等待着一堆古老的研究。