我知道， 平面测试可以在O（V）来完成（等同O（E），因为平面图有O（V）边缘）的时间。
我不知道，如果它可以在网上O（1）来完成，因为每个边缘添加（仍然是O（E）时总）分期时间。
换言之，在表示图形和对象的边缘的约束使得所表示的曲线图是平面的，一个数据库表多少时间必须在DBMS负责管理约束采取来验证每个提议的插入？ （为了简化起见，假设不存在缺失。）必须将其重新运行O（v）的平面性测试算法来测试插入的每个提议的插入或组中的一个？
Answer 1:
一些调查研究后，它看来，答案是“是”，有网上的算法，但“不”有没有用O（1）摊销运行时间。
这里是1999年的论文在杂志的ACM中， 与应用程序完全动态平面测试 ，其中作者写道：
特别地，我们考虑在平面图G以下三个操作：（i）如所得图表保持平面插入的边缘; （ⅱ）删除的边缘; 和（iii）测试的边缘是否可以被添加到图形而不违反平面性。 我们将展示如何（N ^ 2/3）时支撑每个上述操作的O，其中n是图中的顶点的数量。 该界测试和缺失是最坏的情况，而开往插入摊销。
我还发现了一个1989年的纸张，抽象的增量平面测试自称为O（log n）的开往边缘插入，但我不知道，如果他们的技术覆盖缺失也是如此。
1999年的文件还指O（反阿克曼（总的操作，n））的算法没有缺失的情况下，在1992年的论文，讨论了快速增量面性 ，但CiteSeer下跌的时刻，所以我LL后来读的细节。
正在删除我的应用程序非常有用，并且可以访问该J. ACM纸，我要在摊销为O（n ^ 2/3）战略进一步阅读。
文章来源: Are there any online algorithms for planarity testing?
