Improved Compression of the Okamura-Seymour Metric

Authors Shay Mozes , Nathan Wallheimer , Oren Weimann



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.27.pdf
  • Filesize: 1.18 MB
  • 19 pages

Document Identifiers

Author Details

Shay Mozes
  • Reichman University, Herzliya, Israel
Nathan Wallheimer
  • University of Haifa, Israel
Oren Weimann
  • University of Haifa, Israel

Cite AsGet BibTex

Shay Mozes, Nathan Wallheimer, and Oren Weimann. Improved Compression of the Okamura-Seymour Metric. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.27

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 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³).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Shortest paths
  • planar graphs
  • metric compression
  • distance oracles

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Amir Abboud, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Near-optimal compression for the planar graph metric. In 29th SODA, pages 530-549, 2018. Google Scholar
  2. Amitabh Basu and Anupam Gupta. Steiner point removal in graph metrics, 2008. Unpublished Manuscript, available from URL: https://www.ams.jhu.edu/~abasu9/papers/SPR.pdf.
  3. Jon Louis Bentley. Solutions to klee’s rectangle problems. Unpublished manuscript, pages 282-300, 1977. Google Scholar
  4. Guy E. Blelloch and Arash Farzan. Succinct representations of separable graphs. In 21st CPM, pages 138-150, 2010. Google Scholar
  5. Hubert T.-H. Chan, Donglin Xia, Goran Konjevod, and Andréa W. Richa. A tight lower bound for the steiner point removal problem on trees. In 9th APPROX, pages 70-81, 2006. Google Scholar
  6. Hsien-Chih Chang, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Near-optimal distance emulator for planar graphs. In 26th ESA, pages 16:1-16:17, 2018. Google Scholar
  7. Hsien-Chih Chang and Tim Ophelders. Planar emulators for monge matrices. In 32nd CCCG, pages 141-147, 2020. Google Scholar
  8. Yun Kuen Cheung. Steiner point removal - distant terminals don't (really) bother. In 29th SODA, pages 1353-1360, 2018. Google Scholar
  9. Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger. Graph minors for preserving terminal distances approximately - lower and upper bounds. In 43rd ICALP, pages 131:1-131:14, 2016. Google Scholar
  10. Yi-Ting Chiang, Ching-Chi Lin, and Hsueh-I Lu. Orderly spanning trees with applications to graph encoding and graph drawing. In 22nd SODA, pages 506-515, 2001. Google Scholar
  11. James R Driscoll, Neil Sarnak, Daniel D Sleator, and Robert E Tarjan. Making data structures persistent. Journal of computer and system sciences, 38(1):86-124, 1989. Google Scholar
  12. David Eisenstat and Philip N Klein. Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. In 45th STOC, pages 735-744, 2013. Google Scholar
  13. Arnold Filtser. Steiner point removal with distortion O(log k). In 29th SODA, pages 1361-1373, 2018. Google Scholar
  14. Arnold Filtser, Robert Krauthgamer, and Ohad Trabelsi. Relaxed voronoi: A simple framework for terminal-clustering problems. In 2nd SOSA, pages 10:1-10:14, 2019. Google Scholar
  15. Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen. Truly subquadratic exact distance oracles with constant query time for planar graphs. arXiv preprint, 2020. URL: http://arxiv.org/abs/2009.14716.
  16. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85-112, 2004. Google Scholar
  17. Gramoz Goranci, Monika Henzinger, and Pan Peng. Improved guarantees for vertex sparsification in planar graphs. In 25th ESA, pages 44:1-44:14, 2017. Google Scholar
  18. Anupam Gupta. Steiner points in tree metrics don't (really) help. In 12th SODA, pages 220-227, 2001. Google Scholar
  19. Lior Kamma, Robert Krauthgamer, and Huy L. Nguyen. Cutting corners cheaply, or how to remove steiner points. SIAM Journal of Computing, 44(4):975-995, 2015. Google Scholar
  20. Richard M. Karp and Michael O. Rabin. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31(2):249-260, 1987. Google Scholar
  21. Ken-ichi Kawarabayashi, Philip N Klein, and Christian Sommer. Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In 38th ICALP, pages 135-146, 2011. Google Scholar
  22. Philip N Klein. Multiple-source shortest paths in planar graphs. In 16th SODA, volume 5, pages 146-155, 2005. Google Scholar
  23. Robert Krauthgamer, Huy L Nguyen, and Tamar Zondiner. Preserving terminal distances using minors. SIAM Journal on Discrete Mathematics, 28(1):127-141, 2014. Google Scholar
  24. Robert Krauthgamer and Tamar Zondiner. Preserving terminal distances using minors. In 39th ICALP, pages 594-605, 2012. Google Scholar
  25. Jason Li and Merav Parter. Planar diameter via metric compression. In 51st STOC, pages 152-163, 2019. Google Scholar
  26. J. Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In 38th FOCS, pages 118-126, 1997. Google Scholar
  27. Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145-147, 1972. Google Scholar
  28. Maciej M Sysło and Andrzej Proskurowski. On halin graphs. In Graph Theory, pages 248-256. Springer, 1983. Google Scholar
  29. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM, 51(6):993-1024, 2004. Google Scholar
  30. György Turán. On the succinct representation of graphs. Discrete Applied Mathematics, 8(3):289-294, 1984. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail