{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T04:37:03Z","timestamp":1766378223958},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"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":[[2011,7]]},"DOI":"10.1007\/s00453-009-9357-5","type":"journal-article","created":{"date-parts":[[2009,8,31]],"date-time":"2009-08-31T15:28:28Z","timestamp":1251732508000},"page":"484-504","source":"Crossref","is-referenced-by-count":15,"title":["Crossing Number and Weighted Crossing Number of\u00a0Near-Planar Graphs"],"prefix":"10.1007","volume":"60","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,9,1]]},"reference":[{"key":"9357_CR1","unstructured":"Bennett, C., Ryall, J., Spalteholz, L., Gooch, A.: The aesthetics of graph visualization. In: Cunningham, D.W., Meyer, G.W., Neumann, L., Dunning, A., Paricio, R. (eds.) Computational Aesthetics 2007, pp.\u00a057\u201364. Eurographics Association (2007)"},{"issue":"2","key":"9357_CR2","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S.N. Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9357_CR3","doi-asserted-by":"crossref","first-page":"365","DOI":"10.4064\/aa-81-4-365-367","volume":"LXXXI","author":"G. Elekes","year":"1997","unstructured":"Elekes, G.: On the number of sums and products. Acta Arith. LXXXI(4), 365\u2013367 (1997)","journal-title":"Acta Arith."},{"key":"9357_CR4","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. Freeman, New York (1979)"},{"key":"9357_CR5","doi-asserted-by":"crossref","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 J. Algebr. Discrete Methods 4, 312\u2013316 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9357_CR6","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/s00453-004-1128-8","volume":"41","author":"C. Gutwenger","year":"2005","unstructured":"Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. Algorithmica 41, 289\u2013308 (2005)","journal-title":"Algorithmica"},{"key":"9357_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/978-3-540-70904-6_17","volume-title":"GD 2006","author":"P. Hlinen\u00fd","year":"2007","unstructured":"Hlinen\u00fd, P., Salazar, G.: On the crossing number of almost planar graphs. In: Kaufmann, M., Wagner,\u00a0D. (eds.) GD 2006. Lecture Notes in Computer Science, vol. 4372, pp. 162\u2013173. Springer, Berlin (2007)"},{"key":"9357_CR8","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2, 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"key":"9357_CR9","first-page":"85","volume":"47","author":"M. Juvan","year":"1997","unstructured":"Juvan, M., Marin\u010dek, J., Mohar, B.: Elimination of local bridges. Math. Slovaca 47, 85\u201392 (1997)","journal-title":"Math. Slovaca"},{"key":"9357_CR10","volume-title":"Complexity Issues in VLSI","author":"F.T. Leighton","year":"1983","unstructured":"Leighton, F.T.: Complexity Issues in VLSI. MIT Press, Cambridge (1983)"},{"key":"9357_CR11","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF01744433","volume":"17","author":"F.T. Leighton","year":"1984","unstructured":"Leighton, F.T.: New lower bound techniques for vlsi. Math. Syst. Theory 17, 47\u201370 (1984)","journal-title":"Math. Syst. Theory"},{"key":"9357_CR12","doi-asserted-by":"crossref","unstructured":"Liebers, A.: Planarizing Graphs\u2014A Survey and Annotated Bibliography, vol. 5 (2001)","DOI":"10.7155\/jgaa.00032"},{"issue":"5&6","key":"9357_CR13","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/BF01758776","volume":"7","author":"B. Mishra","year":"1992","unstructured":"Mishra, B., Tarjan, R.E.: A linear-time algorithm for finding an ambitus. Algorithmica 7(5&6), 521\u2013554 (1992)","journal-title":"Algorithmica"},{"key":"9357_CR14","first-page":"301","volume":"30","author":"B. Mohar","year":"2006","unstructured":"Mohar, B.: On the crossing number of almost planar graphs. Informatica 30, 301\u2013303 (2006)","journal-title":"Informatica"},{"key":"9357_CR15","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)"},{"issue":"2","key":"9357_CR16","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0953-5438(00)00032-1","volume":"13","author":"H.C. Purchase","year":"2000","unstructured":"Purchase, H.C.: Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interact. Comput. 13(2), 147\u2013162 (2000)","journal-title":"Interact. Comput."},{"key":"9357_CR17","first-page":"405","volume":"31","author":"A. Riskin","year":"1996","unstructured":"Riskin, A.: The crossing number of a cubic plane polyhedral map plus an edge. Stud. Sci. Math. Hung. 31, 405\u2013413 (1996)","journal-title":"Stud. Sci. Math. Hung."},{"key":"9357_CR18","series-title":"Bolyai Society Mathematical Studies","first-page":"179","volume-title":"Intuitive Geometry","author":"F. Shahrokhi","year":"1997","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L.A., Vrt\u2019o, I.: Crossing numbers: bounds and applications. In: Barany, I., B\u00f6r\u00f6czky, K. (eds.) Intuitive Geometry, Budapest, 1995. Bolyai Society Mathematical Studies, vol. 6, pp. 179\u2013206. Akademia Kiado, Budapest (1997)"},{"key":"9357_CR19","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1112\/S0024609305004261","volume":"37","author":"J. Solymosi","year":"2005","unstructured":"Solymosi, J.: On the number of sums and products. Bull. Lond. Math. Soc. 37, 491\u2013494 (2005)","journal-title":"Bull. Lond. Math. Soc."},{"key":"9357_CR20","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0012-365X(03)00317-0","volume":"276","author":"L.A. Sz\u00e9kely","year":"2004","unstructured":"Sz\u00e9kely, L.A.: A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math. 276, 331\u2013352 (2004)","journal-title":"Discrete Math."},{"key":"9357_CR21","series-title":"Cambridge Studies in Advanced Mathematics","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511755149","volume-title":"Additive Combinatorics","author":"T. Tao","year":"2006","unstructured":"Tao, T., Vu, V.H.: Additive Combinatorics. Cambridge Studies in Advanced Mathematics, vol. 105. Cambridge University Press, Cambridge (2006)"},{"key":"9357_CR22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0012-365X(75)90032-1","volume":"12","author":"W.T. Tutte","year":"1975","unstructured":"Tutte, W.T.: Separation of vertices by a circuit. Discrete Math. 12, 173\u2013184 (1975)","journal-title":"Discrete Math."},{"key":"9357_CR23","unstructured":"Vrt\u2019o, I.: Crossing number of graphs: a bibliography. ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9357-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9357-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9357-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T14:58:05Z","timestamp":1685113085000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9357-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,1]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["9357"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9357-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,1]]}}}