algorithm - 是否有用于平面度测试的在线算法？

Question

我知道planarity testing可以在 O(v)(相当于 O(e)，因为平面图有 O(v) 条边)的时间内完成。

我想知道它是否可以在 O(1) 分摊时间内在线完成，因为添加了每条边(总体上仍然是 O(e) 时间)。

换句话说，在表示图的边的数据库表中，并受制于所表示的图是平面的约束，负责管理约束的 DBMS 必须花费多少时间来验证每个建议的插入？ (为简化起见，假设没有删除。)它是否必须重新运行 O(v) 平面度测试算法之一来测试每个建议的插入或插入组？

Answer 1

经过更多研究后，答案似乎是"is"，有在线算法，但“否”没有 O(1) 摊销运行时间。

这是 1999 年发表在 ACM 杂志上的一篇论文，Fully dynamic planarity testing with applications ，其中作者写道:

In particular, we consider the following three operations on a planar graph G: (i) insert an edge if the resultant graph remains planar; (ii) delete an edge; and (iii) test whether an edge could be added to the graph without violating planarity. We show how to support each of the above operations in O(n^2/3) time, where n is the number of vertices in the graph. The bound for tests and deletions is worst-case, while the bound for insertions is amortized.

我还找到了一篇 1989 年论文的摘要，Incremental planarity testing声称边缘插入的 O(log n) 界限，但我不确定他们的技术是否也包括删除。

1999 年的论文还提到了针对无删除情况的 O(inverse-ackermann(total-operations, n)) 算法，在 1992 年的论文 Fast incremental planarity testing 中进行了讨论。 , 但 CiteSeer 目前已关闭，所以我稍后会阅读详细信息。

删除对我的应用程序很有用，并且可以访问 J.ACM 论文，我将进一步阅读摊销 O(n^2/3) 策略。