jacob说：“没错，这就是问题的精髓。”

终于在1996年，4名计算机科学家发表了一种测试图形的可平面性的算法。可惜的是，这个算法所涉及到的计算步骤非常多，其步骤数量基本上与图形中的节点数的平方根成正比。作为一个算法，这并不算很高效。而自这一算法被发表以来，一直没能得到改进。直到现在。

holm和rotenberg在翻阅他们去年发表的论文时，惊喜地发现论文中含有一个可得出更好算法的重要见解，解决了改进这个算法时会遇到的一个主要障碍。今年6月，他们提交了一份新的论文，文中详细描述了一种方法，能指数级地改进检验图形的可平面性的算法。

在检查图形的平面性方面，新算法的步骤数量正比于图形中的节点数的对数的立方，这比1996年的算法要快得多。他们利用了可平面图的这样一个特点，即一个相同的可平面图有着多种不同的绘制方式，在不同的绘制方式中，点与点之间的连接仍是相同的，但连线之间的相对位置却有可能不同。

现在，如果添加一条连接平面图中的两个节点的额外的连线，比如让这节点1和6相连，那么假如从a开始，它需要连续翻转两次才能使节点1和6的相连不与其他任何边交叉。

holm和rotenberg发现，在2019年的论文中涵盖了这样一个信息，利用这个信息，可以为可平面图找到“更好的绘制方法”。这里的更好的绘制方法，指的是当有额外的连线被添加到图中时，“更好”的绘制方法能比其他绘制方法提供更优的起始位置，使得当额外的连线被添加之后，只需经过很少步骤的翻转，就能维持图形的可平面性不被破坏的状况。

当他们很快意识到这一点，就产生了一个概念上的非常简单的新算法。

新的算法在每次执行一次翻转时，都会生成两种结果中的一种：要么是算法找到了一种能维持可平面性的添加所需边的方法；要么是算法得出结论发现没有可以添加所需边的方法，于是在下一个翻转时撤销上一个翻转。

新的方法或许目前来看还不够完美，对于大多数解决现实问题的应用程序来说，它所需要的步骤还是没有最小化，但这已经是在朝着解决这类问题的最佳可能算法靠近的一个重大突破。