{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:11:48Z","timestamp":1761621108669},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,7,19]],"date-time":"2012-07-19T00:00:00Z","timestamp":1342656000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s00454-012-9440-6","type":"journal-article","created":{"date-parts":[[2012,7,19]],"date-time":"2012-07-19T08:37:27Z","timestamp":1342687047000},"page":"348-358","source":"Crossref","is-referenced-by-count":18,"title":["Hardness of Approximation for Crossing Number"],"prefix":"10.1007","volume":"49","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,7,19]]},"reference":[{"issue":"2","key":"9440_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1137\/080729256","volume":"40","author":"C. Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Svensson, O.: Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM J. Comput. 40(2), 567\u2013596 (2011)","journal-title":"SIAM J. Comput."},{"key":"9440_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999)"},{"issue":"2","key":"9440_CR3","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1137\/05062706X","volume":"20","author":"D. Bokal","year":"2006","unstructured":"Bokal, D., Fijav\u017e, G., Mohar, B.: The minor crossing number. SIAM J. Discrete Math. 20(2), 344\u2013356 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"9440_CR4","first-page":"68","volume-title":"Proc. SoCG 2010","author":"S. Cabello","year":"2010","unstructured":"Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number hard. In: Proc. SoCG 2010, pp.\u00a068\u201376 (2010). See http:\/\/arxiv.org\/abs\/1203.5944 for the full version"},{"issue":"1","key":"9440_CR5","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/net.3230210106","volume":"21","author":"S. Chopra","year":"1991","unstructured":"Chopra, S., Rao, M.R.: On the multiway cut polyhedron. Networks 21(1), 51\u201389 (1991)","journal-title":"Networks"},{"key":"9440_CR6","first-page":"303","volume-title":"Proc. STOC 2011","author":"J. Chuzhoy","year":"2011","unstructured":"Chuzhoy, J.: An algorithm for the graph crossing number problem. In: Proc. STOC 2011, pp.\u00a0303\u2013312 (2011). See http:\/\/arxiv.org\/abs\/1012.0255 for the full version"},{"issue":"5","key":"9440_CR7","doi-asserted-by":"crossref","first-page":"1376","DOI":"10.1137\/06065430X","volume":"36","author":"J. Chuzhoy","year":"2007","unstructured":"Chuzhoy, J., Naor, J.: The hardness of metric labeling. SIAM J. Comput. 36(5), 1376\u20131386 (2007)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9440_CR8","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"9440_CR9","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R. Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, 4th edn. Graduate Texts in Mathematics, vol.\u00a0173. Springer, Berlin (2010)","edition":"4"},{"key":"9440_CR10","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"},{"issue":"2","key":"9440_CR11","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M. Grohe","year":"2004","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. J.\u00a0Comput. Syst. Sci. 68(2), 285\u2013302 (2004)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"4","key":"9440_CR12","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/j.jctb.2005.09.009","volume":"96","author":"P. Hlin\u011bn\u00fd","year":"2006","unstructured":"Hlin\u011bn\u00fd, P.: Crossing number is hard for cubic graphs. J.\u00a0Comb. Theory, Ser. B 96(4), 455\u2013471 (2006)","journal-title":"J.\u00a0Comb. Theory, Ser. B"},{"issue":"2","key":"9440_CR13","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1137\/070685671","volume":"39","author":"H.J. Karloff","year":"2009","unstructured":"Karloff, H.J., Khot, S., Mehta, A., Rabani, Y.: On earthmover distance, metric labeling, and 0-extension. SIAM J. Comput. 39(2), 371\u2013387 (2009)","journal-title":"SIAM J. Comput."},{"key":"9440_CR14","first-page":"382","volume-title":"Proc. STOC 2007","author":"K.-I. Kawarabayashi","year":"2007","unstructured":"Kawarabayashi, K.-I., Reed, B.: Computing crossing number in linear time. In: Proc. STOC 2007, pp.\u00a0382\u2013390 (2007)"},{"key":"9440_CR15","first-page":"11","volume-title":"Proc. STOC 2008","author":"R. Manokaran","year":"2008","unstructured":"Manokaran, R., Naor, J., Raghavendra, P., Schwartz, R.: SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling. In: Proc. STOC 2008, pp.\u00a011\u201320 (2008)"},{"issue":"3","key":"9440_CR16","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/s00453-009-9343-y","volume":"60","author":"M.J. Pelsmajer","year":"2011","unstructured":"Pelsmajer, M.J., Schaefer, M., \u0160tefankovic, D.: Crossing numbers of graphs with rotation systems. Algorithmica 60(3), 679\u2013702 (2011)","journal-title":"Algorithmica"},{"key":"9440_CR17","unstructured":"Vrt\u2019o, I.: Crossing number of graphs: a bibliography. ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9440-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-012-9440-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9440-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T07:10:21Z","timestamp":1561965021000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-012-9440-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,19]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["9440"],"URL":"https:\/\/doi.org\/10.1007\/s00454-012-9440-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,19]]}}}