2026-07-23T17:31:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17312 2024-03-06T10:59:26Z ddc:004 open_access

Improved Compression of the Okamura-Seymour Metric Mozes, Shay Wallheimer, Nathan Weimann, Oren Shortest paths planar graphs metric compression distance oracles Let G = (V,E) be an undirected unweighted planar graph. Let S = {s_1,…,s_k} be the vertices of some face in G and let T ⊆ V be an arbitrary set of vertices. The Okamura-Seymour metric compression problem asks to compactly encode the S-to-T distances. Consider a vector storing the distances from an arbitrary vertex v to all vertices S = {s_1,…,s_k} 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 p_#, is only O(k³). This resulted in a simple Õ(min{k⁴+|T|, k⋅|T|}) space compression of the Okamura-Seymour metric. We give an alternative proof of the p_# = O(k³) 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 Õ(p_#+k+|T|) space compression of the Okamura-Seymour metric, thus improving the compression of Li and Parter to Õ(min{k³+|T|, k⋅|T|}). (2) An optimal Õ(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 p_# = Θ(k²) for the family of Halin graphs, whereas the VC-dimension argument is limited to showing p_# = O(k³). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shay Mozes and Nathan Wallheimer and Oren Weimann 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.27 urn:nbn:de:0030-drops-173123 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.27 eng https://creativecommons.org/licenses/by/4.0/legalcode