{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:58:18Z","timestamp":1725861498964},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_37","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T15:50:21Z","timestamp":1468943421000},"page":"455-467","source":"Crossref","is-referenced-by-count":3,"title":["Approximating the Maximum Rectilinear Crossing Number"],"prefix":"10.1007","author":[{"given":"Samuel","family":"Bald","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew P.","family":"Johnson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ou","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"37_CR1","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method, chap. 15, pp. 249\u2013258. Wiley, Hoboken (1992)"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Alpert, M., Feder, E., Harborth, H.: The maximum of the maximum rectilinear crossing numbers of $$d$$ -regular graphs of order $$n$$ . Electr. J. Comb. 16(1) (2009)","DOI":"10.37236\/143"},{"issue":"5","key":"37_CR3","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/BF02574701","volume":"6","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: Some provably hard crossing number problems. Discrete Comput. Geom. 6(5), 443\u2013459 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"37_CR4","doi-asserted-by":"crossref","first-page":"1803","DOI":"10.1137\/120872310","volume":"42","author":"S Cabello","year":"2013","unstructured":"Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput. 42(5), 1803\u20131829 (2013)","journal-title":"SIAM J. Comput."},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in pspace. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC 1988, pp. 460\u2013467. ACM, New York (1988)","DOI":"10.1145\/62212.62257"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: An algorithm for the graph crossing number problem. CoRR, abs\/1012.0255 (2010)","DOI":"10.1145\/1993636.1993678"},{"key":"37_CR7","doi-asserted-by":"crossref","first-page":"52","DOI":"10.2307\/2319261","volume":"80","author":"P Erd\u0151s","year":"1973","unstructured":"Erd\u0151s, P., Guy, R.K.: Crossing number problems. Am. Math. Mon. 80, 52\u201358 (1973)","journal-title":"Am. Math. Mon."},{"key":"37_CR8","first-page":"290","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On random graphs. i. Publicationes Math. 6, 290\u2013297 (1959)","journal-title":"Publicationes Math."},{"key":"37_CR9","first-page":"31","volume":"206","author":"E Feder","year":"2010","unstructured":"Feder, E., Harborth, H., Herzberg, S., Klein, S.: The maximum rectilinear crossing number of the Petersen graph. Congr. Numerantium 206, 31\u201340 (2010)","journal-title":"Congr. Numerantium"},{"key":"37_CR10","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/sapm1977562159","volume":"56","author":"W Furry","year":"1977","unstructured":"Furry, W., Kleitman, D.: Maximal rectilinear crossings of cycles. Stud. Appl. Math. 56, 159\u2013167 (1977)","journal-title":"Stud. Appl. Math."},{"issue":"3","key":"37_CR11","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"MR Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods 4(3), 312\u2013316 (1983)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"3","key":"37_CR12","doi-asserted-by":"crossref","first-page":"878","DOI":"10.1137\/090756144","volume":"40","author":"V Guruswami","year":"2011","unstructured":"Guruswami, V., Hstad, J., Manokaran, R., Raghavendra, P., Charikar, M.: Beating the random ordering is hard: every ordering CSP is approximation resistant. SIAM J. Comput. 40(3), 878\u2013914 (2011)","journal-title":"SIAM J. Comput."},{"key":"37_CR13","first-page":"15","volume":"66","author":"H Harborth","year":"1988","unstructured":"Harborth, H.: Drawing of the cycle graph. Congr. Numer. 66, 15\u201322 (1988)","journal-title":"Congr. Numer."},{"issue":"4","key":"37_CR14","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/j.jctb.2005.09.009","volume":"96","author":"P Hlin\u00e9n\u00fd","year":"2006","unstructured":"Hlin\u00e9n\u00fd, P.: Crossing number is hard for cubic graphs. J. Comb. Theory Ser. B 96(4), 455\u2013471 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"key":"37_CR15","unstructured":"Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Obfuscated drawings of planar graphs. CoRR, abs\/0803.0858 (2008)"},{"key":"37_CR16","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/978-1-4614-0110-0","volume-title":"Thirty Essays on Geometric Graph Theory","author":"J Pach","year":"2013","unstructured":"Pach, J., \u00c1brego, B., Fern\u00e1ndez-Merchant, S., Salazar, G.: The rectilinear crossing number of $$K_n$$ : closing in (or are we?). In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 5\u201318. Springer, New York (2013)"},{"key":"37_CR17","first-page":"194","volume":"9","author":"J Pach","year":"2000","unstructured":"Pach, J., T\u00f3th, G.: Thirteen problems on crossing numbers. Geombinatorics 9, 194\u2013207 (2000)","journal-title":"Geombinatorics"},{"key":"37_CR18","doi-asserted-by":"crossref","unstructured":"Pach, J., T\u00f3th, G.: Which crossing number is it anyway? J. Comb. Theory, Ser. B 80(2), 225\u2013246 (2000)","DOI":"10.1006\/jctb.2000.1978"},{"key":"37_CR19","unstructured":"Ringel, G.: Extremal problems in the theory of graphs. In: Fiedler, M. (ed.) Theory of Graphs and Its Applications, Proceedings of Symposium Smolenice 1963, Prague, pp. 85\u201390 (1964)"},{"key":"37_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/978-3-642-11805-0_32","volume-title":"Graph Drawing","author":"M Schaefer","year":"2010","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 334\u2013344. Springer, Heidelberg (2010)"},{"key":"37_CR21","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: The graph crossing number, its variants: a survey. Electron. J. Combin. Dyn. Surv. 21 (2014)","DOI":"10.37236\/2713"},{"issue":"1","key":"37_CR22","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1002\/jgt.3190010105","volume":"1","author":"P Tur\u00e1n","year":"1977","unstructured":"Tur\u00e1n, P.: A note of welcome. J. Graph Theory 1(1), 7\u20139 (1977)","journal-title":"J. Graph Theory"},{"issue":"1\u20133","key":"37_CR23","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1016\/j.tcs.2008.02.032","volume":"396","author":"O Verbitsky","year":"2008","unstructured":"Verbitsky, O.: On the obfuscation complexity of planar graphs. Theor. Comput. Sci. 396(1\u20133), 294\u2013300 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"37_CR24","unstructured":"Weisstein, E.W.: Star polygon (2010)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,19]],"date-time":"2023-08-19T07:46:56Z","timestamp":1692431216000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}