是否有用于平面度测试的在线算法？
我知道 平面度测试 可以在 O(v) 中完成（相当于 O(e)，因为平面图有 O(v) 条边）时间。
我想知道是否可以在 O(1) 摊销时间内在线完成，因为添加每个边（总体上仍然是 O(e) 时间）。
换句话说，在表示图的边缘并受到所表示的图是平面的约束的数据库表中，负责管理约束的 DBMS 必须花费多少时间来验证每个建议的插入？ （为了简化，假设没有删除。）是否必须重新运行 O(v) 平面度测试算法之一来测试每个建议的插入或插入组？
I know that planarity testing can be done in O(v) (equivalently O(e), since planar graphs have O(v) edges) time.
I wonder if it can be done online in O(1) amortized time as each edge is added (still O(e) time overall).
In other words, in a database table representing edges of a graph and subject to a constraint that the represented graph is planar, how much time must the DBMS responsible for managing the constraint take to validate each proposed insertion? (For simplification, assume that there are no deletions.) Must it re-run one of the O(v) planarity testing algorithms to test each proposed insertion or group of insertions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
经过更多研究后，答案似乎是“是”，有在线算法，但“否”没有具有 O(1) 摊销运行时间的算法。
这是 1999 年发表在 ACM 杂志上的论文，全动态平面度测试与应用程序，作者写道：
我还找到了 1989 年论文的摘要，增量平面度测试< /a> 声称边缘插入的 O(log n) 界限，但我不确定他们的技术是否也涵盖删除。
1999 年的论文还参考了 1992 年论文中讨论的无删除情况下的 O(inverse-ackermann(total-operations, n)) 算法，快速增量平面性测试，但 CiteSeer 目前已关闭，所以我会阅读稍后详细介绍。
删除对我的应用程序很有用，并且可以访问 J. ACM 论文，我将进一步阅读摊销 O(n^2/3) 策略。
After some more research it appears that the answer is "yes", there are online algorithms, but "no" there are none with O(1) amortized running time.
Here's a 1999 paper in the Journal of the ACM, Fully dynamic planarity testing with applications, in which the authors wrote:
I also found the abstract of a 1989 paper, Incremental planarity testing claiming an O(log n) bound for edge insertion, but I'm not sure if their technique covers deletion as well.
The 1999 paper also refers to an O(inverse-ackermann(total-operations, n)) algorithm for the case of no deletions, discussed in a 1992 paper, Fast incremental planarity testing, but CiteSeer is down at the moment, so I'll read the details later.
Deletion being useful to my application, and having access to the J. ACM paper, I'm going to read further on the amortized O(n^2/3) strategy.