{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:10:16Z","timestamp":1761621016212,"version":"3.37.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,7,22]],"date-time":"2009-07-22T00:00:00Z","timestamp":1248220800000},"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-9343-y","type":"journal-article","created":{"date-parts":[[2009,7,21]],"date-time":"2009-07-21T14:20:40Z","timestamp":1248186040000},"page":"679-702","source":"Crossref","is-referenced-by-count":12,"title":["Crossing Numbers of Graphs with Rotation Systems"],"prefix":"10.1007","volume":"60","author":[{"given":"Michael J.","family":"Pelsmajer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Schaefer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,7,22]]},"reference":[{"key":"9343_CR1","unstructured":"Archdeacon, D.: Problems in topological graph theory. http:\/\/www.emba.uvm.edu\/~archdeac\/problems\/npcubic.htm . Accessed 11 August 2008"},{"key":"9343_CR2","doi-asserted-by":"crossref","unstructured":"Bokal, D., Fijav\u017e, G., Mohar, B.: Minor-monotone crossing number. In: Felsner, S. (ed.) EuroComb \u201905. Discrete Mathematics and Theoretical Computer Science, vol. AE, pp. 123\u2013128 (2005)","DOI":"10.46298\/dmtcs.3433"},{"key":"9343_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/11809678_52","volume-title":"COCOON","author":"C. Buchheim","year":"2006","unstructured":"Buchheim, C., J\u00fcnger, M., Menze, A., Percan, M.: Bimodal crossing minimization. In: Chen, D.Z., Lee, D.T. (eds.) COCOON. Lecture Notes in Computer Science, vol. 4112, pp. 497\u2013506. Springer, Berlin (2006)"},{"issue":"2","key":"9343_CR4","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1111\/j.2517-6161.1977.tb01624.x","volume":"39","author":"P. Diaconis","year":"1977","unstructured":"Diaconis, P., Graham, R.L.: Spearman\u2019s footrule as a measure of disarray. J. R. Stat. Soc., Ser. B 39(2), 262\u2013268 (1977)","journal-title":"J. R. Stat. Soc., Ser. B"},{"issue":"3","key":"9343_CR5","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9343_CR6","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(3), 312\u2013316 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"4","key":"9343_CR7","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. Combin. Theory, Ser. B 96(4), 455\u2013471 (2006)","journal-title":"J. Combin. Theory, Ser. B"},{"key":"9343_CR8","unstructured":"Kedem, Z.M., Fuchs, H.: On finding several shortest paths in certain graphs. In: 18th Allerton Conference, pp.\u00a0677\u2013686 (1980)"},{"key":"9343_CR9","series-title":"The Art of Computer Programming","volume-title":"Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: Sorting and Searching. The Art of Computer Programming, vol.\u00a03. Addison-Wesley, Reading (1973)"},{"key":"9343_CR10","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/321879.321880","volume":"22","author":"R. Lowrance","year":"1975","unstructured":"Lowrance, R., Wagner, R.A.: An extension of the string-to-string correction problem. J. Assoc. Comput. Mach. 22, 177\u2013183 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"9343_CR11","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(90)90109-B","volume":"35","author":"M. Maes","year":"1990","unstructured":"Maes, M.: On a cyclic string-to-string correction problem. Inf. Process. Lett. 35(2), 73\u201378 (1990)","journal-title":"Inf. Process. Lett."},{"key":"9343_CR12","doi-asserted-by":"crossref","unstructured":"Marzal, A., Barrachina, S.: Speeding up the computation of the edit distance for cyclic strings. In: International Conference on Pattern Recognition, pp.\u00a0891\u2013894 (2000)","DOI":"10.1109\/ICPR.2000.906217"},{"key":"9343_CR13","series-title":"Johns Hopkins Studies in the Mathematical Sciences","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 Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)"},{"issue":"2","key":"9343_CR14","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1006\/jctb.2000.1978","volume":"80","author":"J. Pach","year":"2000","unstructured":"Pach, J., T\u00f3th, G.: Which crossing number is it anyway? J. Combin. Theory, Ser. B 80(2), 225\u2013246 (2000)","journal-title":"J. Combin. Theory, Ser. B"},{"issue":"4","key":"9343_CR15","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/j.jctb.2006.08.001","volume":"97","author":"M.J. Pelsmajer","year":"2007","unstructured":"Pelsmajer, M.J., Schaefer, M., \u0160tefankovi\u010d, D.: Removing even crossings. J. Combin. Theory, Ser. B 97(4), 489\u2013500 (2007)","journal-title":"J. Combin. Theory, Ser. B"},{"key":"9343_CR16","unstructured":"Pelsmajer, M.J., Schaefer, M., \u0160tefankovi\u010d, D.: Crossing number of graphs with rotation systems. In: Graph Drawing (GD 2007) (2007)"},{"key":"9343_CR17","series-title":"Electronic Notes in Discrete Mathematics","first-page":"85","volume-title":"European Conference on Combinatorics, Graph Theory and Applications (EuroComb \u201907)","author":"M.J. Pelsmajer","year":"2007","unstructured":"Pelsmajer, M.J., Schaefer, M., \u0160tefankovi\u010d, D.: Removing even crossings on surfaces. In: Ne\u0161et\u0159il,\u00a0J., M\u00e1rquez, A., Serra, O. (eds.) European Conference on Combinatorics, Graph Theory and Applications (EuroComb \u201907). Electronic Notes in Discrete Mathematics, pp. 85\u201390. Elsevier, Amsterdam (2007)"},{"issue":"1","key":"9343_CR18","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1007\/s00454-008-9058-x","volume":"39","author":"M.J. Pelsmajer","year":"2008","unstructured":"Pelsmajer, M.J., Schaefer, M., \u0160tefankovi\u010d, D.: Odd crossing number and crossing number are not the same. Discrete Comput. Geom. 39(1), 442\u2013454 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"9343_CR19","doi-asserted-by":"crossref","unstructured":"Pelsmajer, M.J., Schaefer, M., \u0160tefankovi\u010d, D.: Removing independently even crossings. Graph Draw. (2009, to appear)","DOI":"10.1007\/978-3-642-11805-0_20"},{"issue":"2","key":"9343_CR20","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","volume":"67","author":"M. Schaefer","year":"2003","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Recognizing string graphs in NP. J. Comput. Syst. Sci. 67(2), 365\u2013380 (2003). Special issue on STOC2002 (Montreal, QC)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20133","key":"9343_CR21","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(1\u20133), 331\u2013352 (2004). 6th International Conference on Graph Theory","journal-title":"Discrete Math."},{"issue":"1","key":"9343_CR22","doi-asserted-by":"crossref","first-page":"32","DOI":"10.26493\/1855-3974.43.506","volume":"1","author":"L.A. Sz\u00e9kely","year":"2008","unstructured":"Sz\u00e9kely, L.A.: An optimality criterion for the crossing number. Ars Math. Contemp. 1(1), 32\u201337 (2008)","journal-title":"Ars Math. Contemp."},{"key":"9343_CR23","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., Van, Vu.: Additive Combinatorics. Cambridge Studies in Advanced Mathematics, vol.\u00a0105. Cambridge University Press, Cambridge (2006)"},{"key":"9343_CR24","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0021-9800(70)80007-2","volume":"8","author":"W.T. Tutte","year":"1970","unstructured":"Tutte, W.T.: Toward a theory of crossing numbers. J. Combin. Theory 8, 45\u201353 (1970)","journal-title":"J. Combin. Theory"},{"key":"9343_CR25","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/800116.803771","volume-title":"Seventh Annual ACM Symposium on Theory of Computing","author":"R.A. Wagner","year":"1975","unstructured":"Wagner, R.A.: On the complexity of the extended string-to-string correction problem. In: Seventh Annual ACM Symposium on Theory of Computing, Albuquerque, 1975, pp. 218\u2013223. ACM, New York (1975)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9343-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9343-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9343-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T07:10:43Z","timestamp":1739257843000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9343-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,22]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["9343"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9343-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2009,7,22]]}}}