Special Issue: Research in Combinatorial Optimization and Applications of COCOA 2021
Guest Editors: Donglei Du (University of New Brunswick, Canada), Lu Han (Beijing University of Posts and Telecommunications, P. R. China), Rolf H. Möhring (Technical University Berlin, Germany) and Chenchen Wu (Tianjin University of Technology, P. R. China)

Abstract

We design succinct encodings of series-parallel, block-cactus and 3-leaf power graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood optimally in the RAM model with logarithmic word size. One salient feature of our representation is that it can achieve optimal space even though the exact space lower bound for these graph classes is not known. For these graph classes, we provide succinct data structures with optimal query support for the first time in the literature. For series-parallel multigraphs, our work also extends the works of Uno et al. (Disc. Math. Alg. and Appl., 2013) and Blelloch and Farzan (CPM, 2010) to produce optimal bounds.

A preliminary version of the results appeared in the proceedings of the 15th Annual International Conference on Combinatorial Optimization and Applications (COCOA’21) [5].

Communicated by Chenchen Wu

Keywords:

References

1. H. Acan, S. Chakraborty, S. Jo and S. R. Satti , Succinct encodings for families of interval graphs, Algorithmica 83(3) (2021) 776–794. Crossref, Web of Science, Google Scholar
2. G. E. Blelloch and A. Farzan , Succinct representations of separable graphs, Combinatorial Pattern Matching, 21st Annual Symposium, CPM 2010, Lecture Notes in Computer Science 6129 (2010), pp. 138–150. Crossref, Google Scholar
3. M. Bodirsky, O. Giménez, M. Kang and M. Noy , Enumeration and limit laws for series-parallel graphs, European Journal of Combinatorics 28(8) (2007) 2091–2105. Crossref, Web of Science, Google Scholar
4. A. Brandstädt and V. B. Le , Structure and linear time recognition of 3-leaf powers, Information Processing Letters 98(4) (2006) 133–138. Crossref, Web of Science, Google Scholar
5. S. Chakraborty, S. Jo, K. Sadakane and S. R. Satti , Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs, Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Lecture Notes in Computer Science 13135 (2021), pp. 416–430. Crossref, Google Scholar
6. S. Chakraborty, S. Jo, K. Sadakane and S. R. Satti , Succinct data structures for small clique-width graphs, 31st Data Compression Conference, DCC 2021, (2021), pp. 133–142. Crossref, Google Scholar
7. C. Chauve, É. Fusy and J. O. Lumbroso , An exact enumeration of distance-hereditary graphs, Proceedings of the 14th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2017, (2017), pp. 31–45. Crossref, Google Scholar
8. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein , Introduction to Algorithms, 3rd Edition (MIT Press, 2009). Google Scholar
9. R. Diestel , Graph Theory, 4th Edition (Springer, 2012). Google Scholar
10. H. El-Zein, M. Lewenstein, J. I. Munro, V. Raman and T. M. Chan , On the succinct representation of equivalence classes, Algorithmica 78(3) (2017) 1020–1040. Crossref, Web of Science, Google Scholar
11. A. Farzan and S. Kamali , Compact navigation and distance oracles for graphs with small treewidth, Algorithmica 69(1) (2014) 92–116. Crossref, Web of Science, Google Scholar
12. A. Farzan and J. I. Munro , Succinct encoding of arbitrary graphs, Theoretical Computer Science 513 (2013) 38–52. Crossref, Web of Science, Google Scholar
13. A. Farzan and J. I. Munro , A uniform paradigm to succinctly encode various families of trees, Algorithmica 68(1) (2014) 16–40. Crossref, Web of Science, Google Scholar
14. Y. Gurevich, L. J. Stockmeyer and U. Vishkin , Solving NP-Hard problems on graphs that are almost trees and an application to facility location problems, Journal of the ACM 31(3) (1984) 459–473. Crossref, Web of Science, Google Scholar
15. K. Husimi , Note on mayers’ theory of cluster integrals, The Journal of Chemical Physics 18(5) (1950) 682–684. Crossref, Web of Science, Google Scholar
16. G. J. Jacobson, Succinct static data structures, PhD thesis, Carnegie Mellon University (1998). Google Scholar
17. J. I. Munro and V. Raman , Succinct representation of balanced parentheses and static trees, SIAM Journal on Computing 31(3) (2001) 762–776. Crossref, Google Scholar
18. J. I. Munro and K. Wu , Succinct data structures for chordal graphs, 29th International Symposium on Algorithms and Computation, ISAAC 2018, LIPIcs 123 (2018), pp. 67:1–67:12. Google Scholar
19. J. I. Munro and P. K. Nicholson , Compressed representations of graphs, Encyclopedia of Algorithms, 2016, pp. 382–386. Crossref, Google Scholar
20. G. Navarro , Compact Data Structures - A Practical Approach (Cambridge University Press, 2016). Crossref, Google Scholar
21. G. Navarro and K. Sadakane , Fully functional static and dynamic succinct trees, ACM Transactions on Algorithms 10(3) (2014) 16:1–16:39. Crossref, Web of Science, Google Scholar
22. R. Raman and S. R. Satti , Succinct representations of ordinal trees, Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, Lecture Notes in Computer Science 8066 (2013), pp. 319–332. Crossref, Google Scholar
23. R. Raman, V. Raman and S. R. Satti , Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets, ACM Transactions on Algorithms 3(4) (2007) p. 43. Crossref, Google Scholar
24. J. Riordan and C. E. Shannon , The number of two-terminal series-parallel networks, Journal of Mathematics and Physics 21(1–4) (1942) 83–93. Crossref, Google Scholar
25. K. Sadakane , Compressed Suffix Trees with Full Functionality, Theory of Computing Systems 41(4) (2007) 589–607. Crossref, Web of Science, Google Scholar
26. K. Sumigawa and K. Sadakane , Storing partitions of integers in sublinear space, The Review of Socionetwork Strategies 13(2) (2019) 237–252. Crossref, Web of Science, Google Scholar
27. T. Uno, R. Uehara and S. Nakano , Bounding the number of reduced trees, cographs, and series-parallel graphs by compression, Discrete Mathematics, Algorithms and Applications 5(02) (2013), p. 1360001. Link, Google Scholar
28. J. Valdes, R. E. Tarjan and E. L. Lawler , The recognition of series parallel digraphs, SIAM Journal on Computing 11(2) (1982) 298–313. Crossref, Web of Science, Google Scholar
29. V. A. Voblyi and A. K. Meleshko , Enumeration of labeled block-cactus graphs, Journal of Applied and Industrial Mathematics 8(3) (2014) 422–427. Crossref, Google Scholar