有没有用于平面性测试的在线算法？

Question

我知道平面性检测可以在O(v)（同样是O(e)，因为平面图有O(v)的边）时间内完成。

我想知道是否可以在线上以每添加一条边为O(1)摊销时间完成（总体仍为O(e)时间）。

换句话说，在表示图边的数据库表中，受到约束的图形是平面图，负责管理约束的DBMS需要多长时间来验证每个建议的插入？（为简化起见，假设没有删除。）它必须重新运行其中一个O(v)平面性测试算法来测试每个建议的插入或插入组吗？

- Doug McClean

Answer 1

经过进一步的研究，答案似乎是“是”，有在线算法，但“否”，没有O（1）摊销运行时间的算法。这是1999年ACM期刊上的一篇论文，名为Fully dynamic planarity testing with applications Fully dynamic planarity testing with applications，其中作者写道：特别地，我们考虑平面图G上的以下三个操作：（i）如果结果图保持平面，则插入一条边; （ii）删除一条边; 以及（iii）测试是否可以添加边而不违反平面性。我们展示了如何在O（n ^ 2/3）时间内支持上述每个操作，其中n是图中顶点的数量。测试和删除的边界是最坏情况，而插入的边界是摊销的。

我还发现了一篇1989年论文的摘要，增量可平面性测试声称插入边缘的时间复杂度为O(log n)，但我不确定他们的技术是否也涵盖删除操作。

1999年的论文也提到了无删除情况下的O(inverse-ackermann(total-operations, n))算法，在1992年的一篇快速增量可平面性测试论文中讨论，但目前CiteSeer无法访问，所以我稍后会阅读详细内容。

由于删除对我的应用很有用，并且可以访问 J. ACM 论文，我将进一步阅读平摊时间复杂度为O(n^2/3)的策略。

- Doug McClean

---

感谢您的提问和回答。从技术上讲，答案是“不”，因为您要求O(1)摊销，而这些操作是O(n^2/3)，O(log n)和O(inverse-ackermann...)，每个操作都不是O(1) :-) - ShreevatsaR

是的，完全正确，O(1)部分的答案是否定的，而对于更广泛的在线算法问题，答案是肯定的。我会进行编辑以反映这一点。 - Doug McClean

我只想补充一下，目前已知的最快完全动态算法具有$O(\sqrt{n})$的摊销更新时间。http://www.sciencedirect.com/science/article/pii/S0022000096900021 - eig