论文标题
改善了冈村 - 西摩度量的压缩
Improved Compression of the Okamura-Seymour Metric
论文作者
论文摘要
令$ g =（v，e）$为未向未加权的平面图。考虑一个矢量存储从任意顶点$ v $到所有顶点的距离$ s = \ {s_1，s_2，\ ldots，s_k \} $按其周期顺序。 $ v $的模式是通过在该向量的每对连续值之间的差来获得的。在Stoc'19中，Li和Parter使用VC-Dimension参数来表明，在平面图中，不同模式的数量（表示为$ x $）仅为$ O（k^3）$。这导致了一个简单的压缩方案，需要$ \ tilde o（\ min \ {k^4+| t |，k \ cdot | t | \}）$空间以编码$ s $和终端顶点的子集$ t \ subseteq v $之间的距离。这被称为Okamura-Seymour公制压缩问题。 我们给出了$ x = o（k^3）$绑定的替代证明，该证明利用了超出VC-dimension参数的平面度。也就是说，我们的证明依赖于切割周期双重性，以及$ s $的顶点之间的距离是$ k $的。我们的方法意味着以下内容： （1）$ \ tilde {o}（x+k+| t |）$ okamura-seymour公制的空间压缩，从而将li和parter的压缩提高到$ \ tilde o（\ min \ min \ \ s^3+| t |，k \ cdot | t | \}）$。 （2）最佳$ \ tilde {o}（k+| t |）$ okamura-seymour公制的空间压缩，如果$ t $的顶点在$ g $中诱导连接的组件。 （3）Halin图的家族的$ x =θ（k^2）$的紧密界限，而VC-Dimension参数仅限于显示$ x = o（k^3）$。
Let $G=(V,E)$ be an undirected unweighted planar graph. Consider a vector storing the distances from an arbitrary vertex $v$ to all vertices $S = \{ s_1 , s_2 , \ldots , s_k \}$ of a single face in their cyclic order. The pattern of $v$ is obtained by taking the difference between every pair of consecutive values of this vector. In STOC'19, Li and Parter used a VC-dimension argument to show that in planar graphs, the number of distinct patterns, denoted $x$, is only $O(k^3)$. This resulted in a simple compression scheme requiring $\tilde O(\min \{ k^4+|T|, k\cdot |T|\})$ space to encode the distances between $S$ and a subset of terminal vertices $T \subseteq V$. This is known as the Okamura-Seymour metric compression problem. We give an alternative proof of the $x=O(k^3)$ bound that exploits planarity beyond the VC-dimension argument. Namely, our proof relies on cut-cycle duality, as well as on the fact that distances among vertices of $S$ are bounded by $k$. Our method implies the following: (1) An $\tilde{O}(x+k+|T|)$ space compression of the Okamura-Seymour metric, thus improving the compression of Li and Parter to $\tilde O(\min \{k^3+|T|,k \cdot |T| \})$. (2) An optimal $\tilde{O}(k+|T|)$ space compression of the Okamura-Seymour metric, in the case where the vertices of $T$ induce a connected component in $G$. (3) A tight bound of $x = Θ(k^2)$ for the family of Halin graphs, whereas the VC-dimension argument is limited to showing $x=O(k^3)$.
