{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:21:49Z","timestamp":1760440909374},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135088"},{"type":"electronic","value":"9783642135095"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13509-5_13","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T09:19:57Z","timestamp":1277198397000},"page":"138-150","source":"Crossref","is-referenced-by-count":22,"title":["Succinct Representations of Separable Graphs"],"prefix":"10.1007","author":[{"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arash","family":"Farzan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1145\/1062745.1062789","volume-title":"WWW 2005: Special interest tracks and posters of the 14th international conference on World Wide Web","author":"A. Gulli","year":"2005","unstructured":"Gulli, A., Signorini, A.: The indexable web is more than 11.5 billion pages. In: WWW 2005: Special interest tracks and posters of the 14th international conference on World Wide Web, pp. 902\u2013903. ACM, New York (2005)"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-540-75530-2_11","volume-title":"String Processing and Information Retrieval","author":"F. Claude","year":"2007","unstructured":"Claude, F., Navarro, G.: A fast and compact web graph representation. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol.\u00a04726, pp. 118\u2013129. Springer, Heidelberg (2007)"},{"issue":"1-6","key":"13_CR3","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S1389-1286(00)00083-9","volume":"33","author":"A. Broder","year":"2000","unstructured":"Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.: Graph structure in the web. Comput. Netw.\u00a033(1-6), 309\u2013320 (2000)","journal-title":"Comput. Netw."},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1109\/DCC.2001.917151","volume-title":"DCC 2001: Proceedings of the Data Compression Conference","author":"M. Adler","year":"2001","unstructured":"Adler, M., Mitzenmacher, M.: Towards compressing web graphs. In: DCC 2001: Proceedings of the Data Compression Conference, Washington, DC, USA, p. 203. IEEE Computer Society, Los Alamitos (2001)"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1109\/DCC.2001.917152","volume-title":"DCC 2001: Data Compression Conference","author":"T. Suel","year":"2001","unstructured":"Suel, T., Yuan, J.: Compressing the graph structure of the web. In: DCC 2001: Data Compression Conference, p. 213. IEEE, Los Alamitos (2001)"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.entcs.2003.12.002","volume":"91","author":"J.I. Munro","year":"2004","unstructured":"Munro, J.I.: Succinct data structures. Electronic Notes in Theoretical Computer Science\u00a091, 3 (2004)","journal-title":"Electronic Notes in Theoretical Computer Science"},{"issue":"2","key":"13_CR7","doi-asserted-by":"publisher","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 Journal on Applied Mathematics\u00a036(2), 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"6","key":"13_CR8","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput.\u00a016(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"13_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"G.L. Miller","year":"1997","unstructured":"Miller, G.L., Teng, S.H., Thurston, W., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. J. ACM\u00a044(1), 1\u201329 (1997)","journal-title":"J. ACM"},{"key":"13_CR10","first-page":"422","volume-title":"FOCS 1988: Foundations of Computer Science","author":"T. Leighton","year":"1988","unstructured":"Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: FOCS 1988: Foundations of Computer Science, pp. 422\u2013431. IEEE, Los Alamitos (1988)"},{"unstructured":"Blandford, D.K., Blelloch, G.E., Kash, I.A.: Compact representations of separable graphs. In: SODA: ACM-SIAM Symposium on Discrete Algorithms (2003)","key":"13_CR11"},{"issue":"4","key":"13_CR12","doi-asserted-by":"publisher","first-page":"43","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\u00a03(4), 43 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/978-3-540-87744-8_33","volume-title":"Algorithms - ESA 2008","author":"A. Farzan","year":"2008","unstructured":"Farzan, A., Munro, J.I.: Succinct representations of arbitrary graphs. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 393\u2013404. Springer, Heidelberg (2008)"},{"unstructured":"Lu, H.I.: Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. In: SODA 2002: Proceedings of ACM-SIAM symposium on Discrete algorithms, pp. 223\u2013224 (2002)","key":"13_CR14"},{"issue":"4","key":"13_CR15","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S. Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math.\u00a05(4), 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0166-218X(84)90126-4","volume":"8","author":"G. Tur\u00e1n","year":"1984","unstructured":"Tur\u00e1n, G.: On the succinct representation of graphs. Discrete Applied Mathematics\u00a08, 289\u2013294 (1984)","journal-title":"Discrete Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Keeler, W.: Short encodings of planar graphs and maps. DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science\u00a058 (1995)","key":"13_CR17","DOI":"10.1016\/0166-218X(93)E0150-W"},{"issue":"3","key":"13_CR18","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/S0097539799359117","volume":"30","author":"X. He","year":"2000","unstructured":"He, X., Kao, M.Y., Lu, H.I.: A fast general methodology for information-theoretically optimal encodings of graphs. SIAM Journal on Computing\u00a030(3), 838\u2013846 (2000)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: 30th Annual Symposium on Foundations of Computer Science, 1989, October 30 \u2013 November 1, pp. 549\u2013554 (1989)","key":"13_CR19","DOI":"10.1109\/SFCS.1989.63533"},{"doi-asserted-by":"crossref","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses, static trees and planar graphs. In: IEEE Symposium on Foundations of Computer Science, pp. 118\u2013126 (1997)","key":"13_CR20","DOI":"10.1109\/SFCS.1997.646100"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BFb0055046","volume-title":"Automata, Languages and Programming","author":"R.C.N. Chuang","year":"1998","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: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 118\u2013129. Springer, Heidelberg (1998)"},{"unstructured":"Chiang, Y.T., Lin, C.C., Lu, H.I.: Orderly spanning trees with applications to graph encoding and graph drawing. In: SODA 2001: ACM-SIAM symposium on Discrete algorithms, pp. 506\u2013515 (2001)","key":"13_CR22"},{"issue":"2-3","key":"13_CR23","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.tcs.2008.08.016","volume":"408","author":"L.C.A.O. Devillers","year":"2008","unstructured":"Devillers, L.C.A.O., Schaeffer, G.: Succinct representations of planar maps. Theor. Comput. Sci.\u00a0408(2-3), 174\u2013187 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR24","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM Journal on Numerical Analysis\u00a016, 346\u2013358 (1979)","journal-title":"SIAM Journal on Numerical Analysis"},{"key":"13_CR25","first-page":"269","volume":"60","author":"V.A. Liskovets","year":"1987","unstructured":"Liskovets, V.A., Walsh, T.R.: Ten steps to counting planar graphs. Congressus Numerantium\u00a060, 269\u2013277 (1987)","journal-title":"Congressus Numerantium"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13509-5_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:39:08Z","timestamp":1606185548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13509-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135088","9783642135095"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13509-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}