是否有用于平面度测试的在线算法？ [英] Are there any online algorithms for planarity testing?

问题描述

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

我想知道是否可以在O（1）摊销时间内在线添加每条边（换句话说，在表示图表边缘并受制于表示图表是平面的约束的数据库表中，如何负责管理约束的DBMS必须花多少时间来验证每个建议的插入？ （为简化起见，假设没有删除。）是否必须重新运行O（v）平面度测试算法之一来测试每个建议的插入或插入组？

解决方案

经过更多研究后，答案似乎是是，存在在线算法，而否则没有O（1）摊销的运行时间。

这是ACM杂志上的1999年论文，使用应用程序进行完全动态的平面度测试，其中作者写道：

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

我还发现了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:

In particular, we consider the following three operations on a planar graph G: (i) insert an edge if the resultant graph remains planar; (ii) delete an edge; and (iii) test whether an edge could be added to the graph without violating planarity. We show how to support each of the above operations in O(n^2/3) time, where n is the number of vertices in the graph. The bound for tests and deletions is worst-case, while the bound for insertions is amortized.

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.

这篇关于是否有用于平面度测试的在线算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！