下载PDF摘要：给定一个可以插入和删除边的动态图，一个自然的问题是该图目前是否允许平面嵌入。我们给出了一般图的一个确定的全动态算法，该算法在每个边插入或删除的时间为$O(\log^3n)$时，保持一个位来指示图当前是否为平面图。与以前的最佳算法[Eppstein，Galil，Italiano，Spencer，1996]相比，这是一个指数级的改进，后者在每次更新时花费摊销$O(\sqrt{n})$时间。