相关疑难解决方法(0)

我知道平面度测试可以在O(v)中进行(等效O(e),因为平面图具有O(v)边)时间.

我想知道它是否可以在O(1)摊销时间在线完成,因为每个边缘被添加(仍然是整个O(e)时间).

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