{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T13:56:24Z","timestamp":1778594184022,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,9,16]],"date-time":"2010-09-16T00:00:00Z","timestamp":1284595200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,2]]},"DOI":"10.1007\/s00453-010-9452-7","type":"journal-article","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T21:48:01Z","timestamp":1284587281000},"page":"224-257","source":"Crossref","is-referenced-by-count":36,"title":["Succinct Representation of Labeled Graphs"],"prefix":"10.1007","volume":"62","author":[{"given":"J\u00e9r\u00e9my","family":"Barbay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Castelli Aleardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meng","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,9,16]]},"reference":[{"key":"9452_CR1","series-title":"LNCS","first-page":"316","volume-title":"Proceedings of the 18th International Symposium on Algorithms and Computation","author":"J. Barbay","year":"2007","unstructured":"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.\u00a04835, pp.\u00a0316\u2013328. Springer, Berlin (2007)"},{"key":"9452_CR2","unstructured":"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"},{"key":"9452_CR3","unstructured":"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.\u00a0680\u2013689 (2007)"},{"issue":"4","key":"9452_CR4","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D. Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"issue":"3","key":"9452_CR5","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"27","author":"F. Bernhart","year":"1979","unstructured":"Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Combin. Theory, Ser. B 27(3), 320\u2013331 (1979)","journal-title":"J. Combin. Theory, Ser. B"},{"key":"9452_CR6","unstructured":"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.\u00a0679\u2013688 (2003)"},{"key":"9452_CR7","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/11534273_13","volume-title":"Proceedings of the 9th Workshop on Algorithms and Data Structures","author":"L. Castelli Aleardi","year":"2005","unstructured":"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\u2013145. Springer, Berlin (2005)"},{"issue":"2\u20133","key":"9452_CR8","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.tcs.2008.08.016","volume":"408","author":"L. Castelli Aleardi","year":"2008","unstructured":"Castelli Aleardi, L., Devillers, O., Schaeffer, G.: Succinct representations of planar maps. Theor. Comput. Sci., 408(2\u20133), 174\u2013187 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9452_CR9","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1137\/S0097539702411381","volume":"34","author":"Y.-T. Chiang","year":"2005","unstructured":"Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications. SIAM J. Comput. 34(4), 924\u2013945 (2005)","journal-title":"SIAM J. Comput."},{"key":"9452_CR10","doi-asserted-by":"crossref","unstructured":"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.\u00a0118\u2013129 (1998)","DOI":"10.1007\/BFb0055046"},{"issue":"1","key":"9452_CR11","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0608002","volume":"8","author":"F.R.K. Chung","year":"1987","unstructured":"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\u201358 (1987)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9452_CR12","unstructured":"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.\u00a0383\u2013391 (1996)"},{"key":"9452_CR13","doi-asserted-by":"crossref","unstructured":"Farzan, A., Munro, J.I.: Succinct representations of arbitrary graphs. In: 16th Annual European Symposium on Algorithms, pp.\u00a0393\u2013404 (2008)","DOI":"10.1007\/978-3-540-87744-8_33"},{"issue":"3","key":"9452_CR14","first-page":"23","volume":"10","author":"C. Gavoille","year":"2008","unstructured":"Gavoille, C., Hanusse, N.: On compact encoding of pagenumber k graphs. Discrete Math. Theor. Comput. Sci. 10(3), 23\u201334 (2008)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"9452_CR15","unstructured":"He, M.: Succinct indexes. PhD thesis, University of Waterloo, December (2007)"},{"key":"9452_CR16","doi-asserted-by":"crossref","unstructured":"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.\u00a0509\u2013520 (2007)","DOI":"10.1007\/978-3-540-73420-8_45"},{"key":"9452_CR17","doi-asserted-by":"crossref","unstructured":"Isenburg, M., Snoeyink J.: Face fixer: compressing polygon meshes with properties. In: Proceedings of the 27th Annual Conference on Computer Graphics, pp.\u00a0263\u2013270 (2000)","DOI":"10.1145\/344779.344919"},{"key":"9452_CR18","doi-asserted-by":"crossref","unstructured":"Jacobson G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"9452_CR19","unstructured":"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.\u00a0575\u2013584 (2007)"},{"issue":"2","key":"9452_CR20","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"9452_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1367064.1367068","volume":"4","author":"H.-I. Lu","year":"2008","unstructured":"Lu, H.-I., Yeh, C.-C.: Balanced parentheses strike back. ACM Trans. Algorithms 4(3), 1\u201313 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"9452_CR22","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"key":"9452_CR23","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Rao, S.S.: Succinct representations of functions. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming, pp.\u00a01006\u20131015 (2004)","DOI":"10.1007\/978-3-540-27836-8_84"},{"key":"9452_CR24","doi-asserted-by":"crossref","unstructured":"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.\u00a0345\u2013356 (2003)","DOI":"10.1007\/3-540-45061-0_29"},{"issue":"4","key":"9452_CR25","doi-asserted-by":"crossref","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R. Raman","year":"2007","unstructured":"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)","journal-title":"ACM Trans. Algorithms"},{"key":"9452_CR26","unstructured":"Rosenberg, A.L.: The DIOGENES design methodology: toward automatic physical layout. In: Proceedings of the International Workshop on Parallel Algorithms & Architectures, pp.\u00a0335\u2013348 (1986)"},{"key":"9452_CR27","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0138\u2013148 (1990)"},{"issue":"2","key":"9452_CR28","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/321694.321704","volume":"19","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Sorting using networks of queues and stacks. J. ACM 19(2), 341\u2013346 (1972)","journal-title":"J. ACM"},{"key":"9452_CR29","doi-asserted-by":"crossref","unstructured":"Yamanaka, K., Nakano, S.-I.: A compact encoding of plane triangulations with efficient query supports. In: 2nd Annual Workshop on Algorithms and Computation, pp.\u00a0120\u2013131 (2008)","DOI":"10.1007\/978-3-540-77891-2_12"},{"issue":"1","key":"9452_CR30","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M. Yannakakis","year":"1989","unstructured":"Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36\u201367 (1989)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9452-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9452-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9452-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T20:28:27Z","timestamp":1559680107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9452-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,16]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["9452"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9452-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9,16]]}}}