问题描述
我知道可以在O（v）（相当于O（e ），因为平面图具有O（v）条边）的时间。
我想知道是否可以在O（1）摊销时间内在线添加每条边（换句话说，在表示图表边缘并受制于表示图表是平面的约束的数据库表中，如何负责管理约束的DBMS必须花多少时间来验证每个建议的插入？ （为简化起见，假设没有删除。）是否必须重新运行O（v）平面度测试算法之一来测试每个建议的插入或插入组？
经过更多研究后，答案似乎是是，存在在线算法，而否则没有O（1）摊销的运行时间。
这是ACM杂志上的1999年论文，，其中作者写道：
我还发现了1989年的摘要论文，声明为O（log n）势必会插入边缘，但是我不确定他们的技术是否也包括删除。
1999年的论文还提到了O（inverse-ackermann（total -operations，n））算法，该算法在1992年的论文，但CiteSeer目前处于关闭状态，因此我将在稍后阅读详细信息。
删除对我的应用程序很有用，并且可以访问J.ACM论文，我将进一步阅读分期偿付的O（n ^ 2/3）策略。
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?
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.
这篇关于是否有用于平面度测试的在线算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！