Abstract
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 OkamuraSeymour metric compression problem asks to compactly encode the StoT 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 VCdimension 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 OkamuraSeymour metric.
We give an alternative proof of the p_# = O(k³) bound that exploits planarity beyond the VCdimension argument. Namely, our proof relies on cutcycle 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 OkamuraSeymour metric, thus improving the compression of Li and Parter to Õ(min{k³+T, k⋅T}).
(2) An optimal Õ(k+T) space compression of the OkamuraSeymour 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 VCdimension argument is limited to showing p_# = O(k³).
BibTeX  Entry
@InProceedings{mozes_et_al:LIPIcs.ISAAC.2022.27,
author = {Mozes, Shay and Wallheimer, Nathan and Weimann, Oren},
title = {{Improved Compression of the OkamuraSeymour Metric}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {27:127:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17312},
URN = {urn:nbn:de:0030drops173123},
doi = {10.4230/LIPIcs.ISAAC.2022.27},
annote = {Keywords: Shortest paths, planar graphs, metric compression, distance oracles}
}
Keywords: 

Shortest paths, planar graphs, metric compression, distance oracles 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 