{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:42:57Z","timestamp":1787323377743,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We prove that it is NP-hard to determine whether the crossing number of an input graph is even or odd.<\/jats:p>","DOI":"10.1137\/17m1137231","type":"journal-article","created":{"date-parts":[[2018,8,3]],"date-time":"2018-08-03T09:01:15Z","timestamp":1533286875000},"page":"1962-1965","source":"Crossref","is-referenced-by-count":1,"title":["Deciding Parity of Graph Crossing Number"],"prefix":"10.1137","volume":"32","author":[{"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carsten","family":"Thomassen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120302"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/05062706X"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9440-6"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/120872310"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/0604033"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.008"},{"key":"atypb7","first-page":"111","author":"Guy R. K.","year":"1972","journal-title":"Berlin"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.09.009"},{"key":"atypb9","unstructured":"P. Hline\u030cny\u0301 and M. Dern\u030ca\u0301r,\n                      Crossing number is hard for kernelization\n                      , in Proceedings of the 32nd International Symposium on Computational Geometry, SoCG 2016, 2016, Boston, MA, LIPIcs Leibniz Int. Proc. Inform. 51, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany, 2016, 42,http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-009-5."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80087-4"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(87)90108-7"},{"key":"atypb12","unstructured":"B. Mohar and C. Thomassen,\n                      Graphs on Surfaces\n                      , Johns Hopkins University Press, Baltimore, MD, 2001."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9343-y"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10097"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. Schaefer,\n                      The graph crossing number and its variants: A survey\n                      , Electron. J. Combin., 2014, DS21.","DOI":"10.37236\/2713"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90006-0"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1137231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:01Z","timestamp":1787320741000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1137231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1137231"],"URL":"https:\/\/doi.org\/10.1137\/17m1137231","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}