Abstract
In many applications, the properties of an object being modeled are stored as labels on vertices or edges of a graph. In this paper, we consider succinct representation of labeled graphs. Our main results are the succinct representations of labeled and multi-labeled graphs (we consider planar triangulations, planar graphs and k-page graphs) to support various label queries efficiently. The additional space cost to store the labels is essentially the information-theoretic minimum. As far as we know, our representations are the first succinct representations of labeled graphs. We also have two preliminary results to achieve the main contribution. First, we design a succinct representation of unlabeled planar triangulations to support the rank/select of edges in ccw (counter clockwise) order in addition to the other operations supported in previous work. Second, we design a succinct representation for a k-page graph when k is large to support various navigational operations more efficiently. In particular, we can test the adjacency of two vertices in O(lg k) time, while previous work uses O(k) time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barbay, J., Castelli Aleardi, L., He, M., Munro, J.I.: Succinct representation of labeled graphs. In: Proceedings of the 18th International Symposium on Algorithms and Computation. LNCS, vol. 4835, pp. 316–328. Springer, Berlin (2007)
Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. Manuscript http://www.cs.uwaterloo.ca/~mhe/research/manuscript/sisabr.pdf
Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 680–689 (2007)
Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275–292 (2005)
Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Combin. Theory, Ser. B 27(3), 320–331 (1979)
Blandford, D.K., Blelloch, G.E., Kash, I.A.: Compact representations of separable graphs. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 679–688 (2003)
Castelli Aleardi, L., Devillers, O., Schaeffer, G.: Succinct representation of triangulations with a boundary. In: Proceedings of the 9th Workshop on Algorithms and Data Structures. LNCS, vol. 3608, pp. 134–145. Springer, Berlin (2005)
Castelli Aleardi, L., Devillers, O., Schaeffer, G.: Succinct representations of planar maps. Theor. Comput. Sci., 408(2–3), 174–187 (2008)
Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications. SIAM J. Comput. 34(4), 924–945 (2005)
Chuang, R.C.-N., Garg, A., He, X., Kao, M.-Y., Lu, H.-I.: Compact encodings of planar graphs via canonical orderings and multiple parentheses. In: Proceedings of the 25th International Colloquium on Automata, Languages and Programming, pp. 118–129 (1998)
Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: a layout problem with applications to VLSI design. SIAM J. Algebr. Discrete Methods 8(1), 33–58 (1987)
Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 383–391 (1996)
Farzan, A., Munro, J.I.: Succinct representations of arbitrary graphs. In: 16th Annual European Symposium on Algorithms, pp. 393–404 (2008)
Gavoille, C., Hanusse, N.: On compact encoding of pagenumber k graphs. Discrete Math. Theor. Comput. Sci. 10(3), 23–34 (2008)
He, M.: Succinct indexes. PhD thesis, University of Waterloo, December (2007)
He, M., Munro, J.I., Rao, S.S.: Succinct ordinal trees based on tree covering. In: Proceedings of the 34st International Colloquium on Automata, Languages and Programming, pp. 509–520 (2007)
Isenburg, M., Snoeyink J.: Face fixer: compressing polygon meshes with properties. In: Proceedings of the 27th Annual Conference on Computer Graphics, pp. 263–270 (2000)
Jacobson G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp. 549–554 (1989)
Jansson, J., Sadakane, K., Sung, W.-K.: Ultra-succinct representation of ordered trees. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 575–584 (2007)
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)
Lu, H.-I., Yeh, C.-C.: Balanced parentheses strike back. ACM Trans. Algorithms 4(3), 1–13 (2008)
Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762–776 (2001)
Munro, J.I., Rao, S.S.: Succinct representations of functions. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming, pp. 1006–1015 (2004)
Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming, pp. 345–356 (2003)
Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007)
Rosenberg, A.L.: The DIOGENES design methodology: toward automatic physical layout. In: Proceedings of the International Workshop on Parallel Algorithms & Architectures, pp. 335–348 (1986)
Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 138–148 (1990)
Tarjan, R.E.: Sorting using networks of queues and stacks. J. ACM 19(2), 341–346 (1972)
Yamanaka, K., Nakano, S.-I.: A compact encoding of plane triangulations with efficient query supports. In: 2nd Annual Workshop on Algorithms and Computation, pp. 120–131 (2008)
Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36–67 (1989)
Author information
Authors and Affiliations
Corresponding author
Additional information
The preliminary version of this paper was published in Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC 2007) [1]. This work was supported by NSERC of Canada, the Canada Research Chairs program, the ERC under the agreement “ERC StG 208471—ExploreMap”. The work was done when the first author was in Cheriton School of Computer Science, University of Waterloo, Canada, and part of the second author’s work was done during his visit to the Computer Science Department of Université Libre de Bruxelles, Belgium.
Rights and permissions
About this article
Cite this article
Barbay, J., Castelli Aleardi, L., He, M. et al. Succinct Representation of Labeled Graphs. Algorithmica 62, 224–257 (2012). https://doi.org/10.1007/s00453-010-9452-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-010-9452-7