{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:45Z","timestamp":1740109245921,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,12,17]],"date-time":"2015-12-17T00:00:00Z","timestamp":1450310400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"National Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"School of Computer Science, Carleton University"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00453-015-0086-7","type":"journal-article","created":{"date-parts":[[2015,12,17]],"date-time":"2015-12-17T15:51:33Z","timestamp":1450367493000},"page":"714-755","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["I\/O-Efficient Path Traversal in Succinct Planar Graphs"],"prefix":"10.1007","volume":"77","author":[{"given":"Craig","family":"Dillabaugh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meng","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Norbert","family":"Zeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,17]]},"reference":[{"key":"86_CR1","unstructured":"Agarwal, P.K., Arge, L., Murali, T.M., Varadarajan, K.R., Vitter, J.S.: I\/O-efficient algorithms for contour-line extraction and planar graph blocking (extended abstract). In: SODA, pp. 117\u2013126 (1998)"},{"issue":"9","key":"86_CR2","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"86_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/11534273_13","volume-title":"WADS","author":"LC Aleardi","year":"2005","unstructured":"Aleardi, L.C., Devillers, O., Schaeffer, G.: Succinct representation of triangulations with a boundary. In: Dehne, F.K.H.A., L\u00f3pez-Ortiz, A., Sack, J.R. (eds.) WADS. Lecture Notes in Computer Science, vol. 3608, pp. 134\u2013145. Springer, Berlin (2005)"},{"issue":"2\u20133","key":"86_CR4","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.tcs.2008.08.016","volume":"408","author":"LC Aleardi","year":"2008","unstructured":"Aleardi, L.C., Devillers, O., Schaeffer, G.: Succinct representations of planar maps. Theor. Comput. Sci. 408(2\u20133), 174\u2013187 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"86_CR5","doi-asserted-by":"crossref","unstructured":"Arge, L., Danner, A., Teh, S.M.: I\/O-efficient point location using persistent b-trees. In: Ladner, R.E. (ed.) ALENEX, pp. 82\u201392, Baltimore, MD (2003)","DOI":"10.1145\/996546.996549"},{"key":"86_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/978-3-540-77120-3_29","volume-title":"ISAAC","author":"J Barbay","year":"2007","unstructured":"Barbay, J., Aleardi, L.C., He, M., Munro, J.I.: Succinct representation of labeled graphs. In: Tokuyama, T. (ed.) ISAAC. Lecture Notes in Computer Science, vol. 4835, pp. 316\u2013328. Springer, Berlin (2007)"},{"issue":"3","key":"86_CR7","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/s00453-002-0969-2","volume":"34","author":"S Baswana","year":"2002","unstructured":"Baswana, S., Sen, S.: Planar graph blocking for external searching. Algorithmica 34(3), 298\u2013308 (2002)","journal-title":"Algorithmica"},{"key":"86_CR8","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., Bose, P., Dobrindt, K., van Kreveld, M.J., Overmars, M.H., de\u00a0Groot, M., Roos, T., Snoeyink, J., Yu, S.: The complexity of rivers in triangulated terrains. In: CCCG, pp. 325\u2013330 (1996)","DOI":"10.1515\/9780773591134-057"},{"issue":"4","key":"86_CR9","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1080\/136588197242310","volume":"11","author":"M Berg de","year":"1997","unstructured":"de Berg, M., van Kreveld, M.J., van Oostrum, R., Overmars, M.H.: Simple traversal of a subdivision without extra storage. Int. J. Geogr. Inf. Sci. 11(4), 359\u2013373 (1997)","journal-title":"Int. J. Geogr. Inf. Sci."},{"issue":"3","key":"86_CR10","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. Comb. Theory Ser. B 27(3), 320\u2013331 (1979)","journal-title":"J. Comb. Theory Ser. B"},{"key":"86_CR11","unstructured":"Blandford, D.K., Blelloch, G.E., Kash, I.A.: Compact representations of separable graphs. In: SODA, pp. 679\u2013688 (2003)"},{"issue":"2","key":"86_CR12","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/2151171.2151173","volume":"8","author":"P Bose","year":"2012","unstructured":"Bose, P., Chen, E.Y., He, M., Maheshwari, A., Morin, P.: Succinct geometric indexes supporting point location queries. ACM Trans. Algorithms 8(2), 10 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"86_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1007\/3-540-40996-3_38","volume-title":"ISAAC","author":"P Bose","year":"2000","unstructured":"Bose, P., Morin, P.: An improved algorithm for subdivision traversal without extra storage. In: Lee, D.T., Teng, S.H. (eds.) ISAAC. Lecture Notes in Computer Science, vol. 1969, pp. 444\u2013455. Springer, Berlin (2000)"},{"issue":"4","key":"86_CR14","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1137\/S0097539702411381","volume":"34","author":"YT 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":"86_CR15","doi-asserted-by":"crossref","unstructured":"Chien, Y.F., Hon, W.K., Shah, R., Vitter, J.S.: Geometric Burrows\u2013Wheeler transform: linking range searching and text indexing. In: DCC, pp. 252\u2013261. IEEE Computer Society (2008)","DOI":"10.1109\/DCC.2008.67"},{"key":"86_CR16","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. ICALP\u201998: Proceedings of the 25th International Colloquium on Automata. Languages and Programming, pp. 118\u2013129. Springer, London (1998)","DOI":"10.1007\/BFb0055046"},{"key":"86_CR17","unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage. In: SODA, pp. 383\u2013391 (1996)"},{"key":"86_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-540-92182-0_13","volume-title":"ISAAC","author":"C Dillabaugh","year":"2008","unstructured":"Dillabaugh, C., He, M., Maheshwari, A.: Succinct and I\/O efficient data structures for traversal in trees. In: Hong, S.H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC. Lecture Notes in Computer Science, vol. 5369, pp. 112\u2013123. Springer, Berlin (2008)"},{"issue":"1\u20132","key":"86_CR19","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s00453-011-9528-z","volume":"63","author":"C Dillabaugh","year":"2012","unstructured":"Dillabaugh, C., He, M., Maheshwari, A.: Succinct and I\/O efficient data structures for traversal in trees. Algorithmica 63(1\u20132), 201\u2013223 (2012)","journal-title":"Algorithmica"},{"key":"86_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/978-3-540-87744-8_33","volume-title":"ESA","author":"A Farzan","year":"2008","unstructured":"Farzan, A., Munro, J.I.: Succinct representations of arbitrary graphs. In: Halperin, D., Mehlhorn, K. (eds.) ESA. Lecture Notes in Computer Science, vol. 5193, pp. 393\u2013404. Springer, Berlin (2008)"},{"issue":"6","key":"86_CR21","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"86_CR22","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":"86_CR23","doi-asserted-by":"crossref","unstructured":"Gold, C., Cormack, S.: Spatially ordered networks and topographic reconstructions. In: Proceedings 2nd International Symposium on Spatial Data Handling, pp. 74\u201385 (1986)","DOI":"10.1080\/02693798708927800"},{"key":"86_CR24","unstructured":"Gold, C.M., Maydell, U.M.: Triangulation and spatial ordering in computer cartography. In: Proceedings Canadian Cartographic Association third annual meeting, pp. 69\u201381 (1978)"},{"key":"86_CR25","first-page":"549","volume":"42","author":"G Jacobson","year":"1989","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. FOCS 42, 549\u2013554 (1989)","journal-title":"FOCS"},{"issue":"1","key":"86_CR26","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"DG Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G.: Optimal search in planar subdivisions. SIAM J. Comput. 12(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"86_CR27","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G Miller","year":"1986","unstructured":"Miller, G.: Balanced cyclic separator for 2-connected planar graphs. J. Comput. Syst. Sci. 32(3), 265\u2013279 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"86_CR28","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses, static trees and planar graphs. In: FOCS, pp. 118\u2013126 (1997)","DOI":"10.1109\/SFCS.1997.646100"},{"issue":"2","key":"86_CR29","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01940646","volume":"16","author":"MH Nodine","year":"1996","unstructured":"Nodine, M.H., Goodrich, M.T., Vitter, J.S.: Blocking for external graph searching. Algorithmica 16(2), 181\u2013214 (1996)","journal-title":"Algorithmica"},{"issue":"4","key":"86_CR30","doi-asserted-by":"crossref","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 3(4), 43 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"86_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/978-3-540-77891-2_12","volume-title":"WALCOM","author":"K Yamanaka","year":"2008","unstructured":"Yamanaka, K., Nakano, S.I.: A compact encoding of plane triangulations with efficient query supports. In: Nakano, S.I., Rahman, M.S. (eds.) WALCOM. Lecture Notes in Computer Science, vol. 4921, pp. 120\u2013131. Springer, Berlin (2008)"},{"key":"86_CR32","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Four pages are necessary and sufficient for planar graphs (extended abstract). In: STOC, pp. 104\u2013108. ACM (1986)","DOI":"10.1145\/12130.12141"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0086-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0086-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0086-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0086-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T05:46:06Z","timestamp":1692164766000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0086-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,17]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["86"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0086-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2015,12,17]]}}}