English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $G=(V,E)$ be an undirected unweighted planar graph. Consider a vectorstoring 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 consecutivevalues of this vector. In STOC'19, Li and Parter used a VC-dimension argumentto show that in planar graphs, the number of distinct patterns, denoted $x$, isonly $O(k^3)$. This resulted in a simple compression scheme requiring $\tildeO(\min \{ k^4+|T|, k\cdot |T|\})$ space to encode the distances between $S$ anda subset of terminal vertices $T \subseteq V$. This is known as theOkamura-Seymour metric compression problem.  We give an alternative proof of the $x=O(k^3)$ bound that exploits planaritybeyond the VC-dimension argument. Namely, our proof relies on cut-cycleduality, as well as on the fact that distances among vertices of $S$ arebounded 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-Seymourmetric, in the case where the vertices of $T$ induce a connected component in$G$.  (3) A tight bound of $x = \Theta(k^2)$ for the family of Halin graphs,whereas the VC-dimension argument is limited to showing $x=O(k^3)$.

Improved Compression of the Okamura-Seymour Metric