是否有平面度测试的在线算法？

Question

我知道平面度测试可以在O（v）中完成（相当于O（e） ），因为平面图具有O（v）边）时间。

我想知道是否可以在O（1）摊销时间在线完成每个边缘的添加（仍然是整个O（e）时间）。

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

Answer 1

经过一些研究后，似乎答案是“是”，有在线算法，但是“不”。没有O（1）摊销的运行时间。

这是1999年ACM杂志上的一篇论文，完全动态的平面性用应用程序测试，作者写道：

  

特别是，我们在平面图G上考虑以下三个操作：（i）如果结果图保持平面，则插入边; （ii）删除边缘; （iii）测试是否可以在不违反平面性的情况下将边缘添加到图形中。我们展示了如何在O（n ^ 2/3）时间内支持上述每个操作，其中n是图中顶点的数量。测试和删除的界限是最坏情况，而插入的界限是分摊的。

我还发现了1989年论文的摘要，增量平面度测试声称O（log n）绑定边缘插入，但我不确定他们的技术是否也包含删除。

1999年的论文还提到了一个关于无删除情况的O（逆ackermann（total-operations，n））算法，在1992年的论文快速增量平面度测试，但CiteSeer目前正在关闭，所以我会读到详情稍后。

删除对我的申请有用，并且可以访问J. ACM论文，我将进一步阅读有关摊销的O（n ^ 2/3）策略。