{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:59:11Z","timestamp":1725544751153},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540327554"},{"type":"electronic","value":"9783540327561"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11682462_54","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T06:50:30Z","timestamp":1140159030000},"page":"580-591","source":"Crossref","is-referenced-by-count":2,"title":["I\/O-Efficient Algorithms on Near-Planar Graphs"],"prefix":"10.1007","author":[{"given":"Herman","family":"Haverkort","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laura","family":"Toma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"54_CR1","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s00453-001-0088-5","volume":"32","author":"J. Abello","year":"2002","unstructured":"Abello, J., Buchsbaum, A.L., Westbrook, J.R.: A functional approach to external graph algorithms. Algorithmica\u00a032(3), 437\u2013458 (2002)","journal-title":"Algorithmica"},{"issue":"9","key":"54_CR2","doi-asserted-by":"publisher","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. Communications of the ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Communications of the ACM"},{"key":"54_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/3-540-45643-0_8","volume-title":"Algorithm Engineering and Experiments","author":"L. Aleksandrov","year":"2002","unstructured":"Aleksandrov, L., Djidjev, H., Guo, H., Maheshwari, A.: Partitioning planar graphs with costs and weights. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol.\u00a02409, pp. 98\u2013110. Springer, Heidelberg (2002)"},{"issue":"1","key":"54_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-003-1021-x","volume":"37","author":"L. Arge","year":"2003","unstructured":"Arge, L.: The buffer tree: A technique for designing batched external data structures. Algorithmica\u00a037(1), 1\u201324 (2003)","journal-title":"Algorithmica"},{"issue":"2","key":"54_CR5","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.jalgor.2004.04.001","volume":"53","author":"L. Arge","year":"2004","unstructured":"Arge, L., Brodal, G.S., Toma, L.: On external memory MST, SSSP and multiway planar graph separation. Journal of Algorithms\u00a053(2), 186\u2013206 (2004)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"54_CR6","doi-asserted-by":"publisher","first-page":"105","DOI":"10.7155\/jgaa.00063","volume":"7","author":"L. Arge","year":"2003","unstructured":"Arge, L., Meyer, U., Toma, L., Zeh, N.: On external-memory planar depth first search. Journal of Graph Algorithms\u00a07(2), 105\u2013129 (2003)","journal-title":"Journal of Graph Algorithms"},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"Arge, L., Toma, L.: Simplified external-memory algorithms for planar DAGs. In: Proc. Scandinavian Workshop on Algorithm Theory, pp. 493\u2013503 (2004)","DOI":"10.1007\/978-3-540-27810-8_42"},{"key":"54_CR8","doi-asserted-by":"crossref","unstructured":"Arge, L., Toma, L., Zeh, N.: I\/O-efficient topological sorting of planar DAGs. In: Proc. ACM Symposium on Parallel Algorithms and Architectures (2003)","DOI":"10.1145\/777412.777427"},{"key":"54_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/3-540-60313-1_151","volume-title":"Algorithms - ESA \u201995","author":"L. Arge","year":"1995","unstructured":"Arge, L., Vengroff, D.E., Vitter, J.S.: External-memory algorithms for processing line segments in geographic information systems. In Proc. Eur. Symp. Algorithms. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol.\u00a0979, pp. 295\u2013310. Springer, Heidelberg (1995)"},{"key":"54_CR10","unstructured":"Arge, L., Zeh, N.: I\/O-efficient strong connectivity and depth-first search for directed planar graphs. In: Proc. IEEE Symp. on Found. of Computer Sc. (2003)"},{"key":"54_CR11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1002\/jgt.3190170308","volume":"17","author":"D. Bienstock","year":"1993","unstructured":"Bienstock, D., Dean, N.: Bounds for rectilinear crossing numbers. Journal of Graph Theory\u00a017, 333\u2013348 (1993)","journal-title":"Journal of Graph Theory"},{"key":"54_CR12","unstructured":"Buchsbaum, A.L., Goldwasser, M., Venkatasubramanian, S., Westbrook, J.R.: On external memory graph traversal. In: Proc. Symposium on Discrete Algorithms, pp. 859\u2013860 (2000)"},{"key":"54_CR13","unstructured":"Chiang, Y.-J., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: Proc. Symposium on Discrete Algorithms, pp. 139\u2013149 (1995)"},{"key":"54_CR14","doi-asserted-by":"crossref","unstructured":"Crauser, A., Ferragina, P., Mehlhorn, K., Meyer, U., Ramos, E.: Randomized external-memory algorithms for some geometric problems. In: Proc. ACM Symposium on Computational Geometry, pp. 259\u2013268 (1998)","DOI":"10.1145\/276884.276914"},{"key":"54_CR15","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0166-218X(00)00220-1","volume":"108","author":"L. Faria","year":"2001","unstructured":"Faria, L., de Figueiredo, C.M.H., de Mendon\u00e7a Neto, C.F.X.: Splitting number is np-complete. Discrete Applied Mathematics\u00a0108, 65\u201383 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"54_CR16","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 Journal on Computing\u00a016, 1004\u20131022 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co, New York (1979)"},{"key":"54_CR18","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is np-complete. SIAM Journal on Algebraic and Discrete Methods\u00a04, 312\u2013316 (1983)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"54_CR19","doi-asserted-by":"crossref","unstructured":"Kumar, V., Schwabe, E.: Improved algorithms and data structures for solving graph problems in external memory. In: Proc. IEEE Symposium on Parallel and Distributed Processing, pp. 169\u2013177 (1996)","DOI":"10.1109\/SPDP.1996.570330"},{"issue":"1","key":"54_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00032","volume":"5","author":"A. Liebers","year":"2001","unstructured":"Liebers, A.: Planarizing graphs\u2014a survey and annotated bibliography. Journal of Graph Algorithms and Applications\u00a05(1), 1\u201374 (2001)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"54_CR21","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 of Applied Math\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal of Applied Math"},{"key":"54_CR22","unstructured":"Maheshwari, A., Zeh, N.: I\/O-optimal algorithms for planar graphs using separators. In: Proc. Symposium on Discrete Algorithms, pp. 372\u2013381 (2002)"},{"key":"54_CR23","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms for Memory Hierarchies","year":"2003","unstructured":"Meyer, U., Sanders, P., Sibeyn, J.F. (eds.): Algorithms for Memory Hierarchies. LNCS, vol.\u00a02625. Springer, Heidelberg (2003)"},{"key":"54_CR24","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF01215922","volume":"17","author":"J. Pach","year":"1997","unstructured":"Pach, J., T\u00f3th, G.: Graphs drawn with few crossings per edge. Combinatorica\u00a017, 427\u2013439 (1997)","journal-title":"Combinatorica"},{"key":"54_CR25","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0166-218X(83)90101-4","volume":"6","author":"T. Watanabe","year":"1983","unstructured":"Watanabe, T., Ae, T., Nakamura, A.: On the np-hardness of edge-deletion and -contraction problems. Discrete Applied Mathematics\u00a06, 63\u201378 (1983)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T03:02:10Z","timestamp":1552359730000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11682462_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}