论文标题
最差的确定性完全动态平面2-Vertex连接性
Worst-case Deterministic Fully-Dynamic Planar 2-vertex Connectivity
论文作者
论文摘要
我们研究具有$ n $顶点的动态平面图，受边缘删除，边缘收缩，脸部边缘插入以及在指定角度的顶点分裂。我们动态地维护了这种平面图的组合嵌入，如连通性和$ 2 $ - vertex-connectitivity（Biconnectivity）的查询。每当连接查询对而不是双连接时，我们都会发现第一个也是最后一个分离它们的cutvertex。 此外，我们通过将最多由两个顶点连接到图形的其余部分连接的子图的嵌入来允许对嵌入的局部更改。 我们使用$ O（n）$大小的数据结构来支持确定性，最差的$ O（\ log^2 n）$时间的所有查询和更新。 Previously, the best bound for fully-dynamic planar biconnectivity (subject to our set of operations) was an amortised $\tilde{O}(\log^3 n)$ for general graphs, and algorithms with worst-case polylogarithmic update times were known only in the partially dynamic (insertion-only or deletion-only) setting.
We study dynamic planar graphs with $n$ vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We dynamically maintain a combinatorial embedding of such a planar graph, subject to connectivity and $2$-vertex-connectivity (biconnectivity) queries between pairs of vertices. Whenever a query pair is connected and not biconnected, we find the first and last cutvertex separating them. Additionally, we allow local changes to the embedding by flipping the embedding of a subgraph that is connected by at most two vertices to the rest of the graph. We support all queries and updates in deterministic, worst-case, $O(\log^2 n)$ time, using an $O(n)$-sized data structure. Previously, the best bound for fully-dynamic planar biconnectivity (subject to our set of operations) was an amortised $\tilde{O}(\log^3 n)$ for general graphs, and algorithms with worst-case polylogarithmic update times were known only in the partially dynamic (insertion-only or deletion-only) setting.
