{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:18:15Z","timestamp":1761621495539,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T00:00:00Z","timestamp":1578873600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T00:00:00Z","timestamp":1578873600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSERC Vanier CSG"},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["CH 897\/2-1"],"award-info":[{"award-number":["CH 897\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SFB 876, project A6"],"award-info":[{"award-number":["SFB 876, project A6"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00453-019-00653-x","type":"journal-article","created":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T06:02:41Z","timestamp":1578895361000},"page":"355-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Crossing Number for Graphs with Bounded Pathwidth"],"prefix":"10.1007","volume":"82","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Chimani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Derka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,13]]},"reference":[{"key":"653_CR1","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M.M., Szemer\u00e9di, E.: Crossing-free subgraphs. In: Hammer, P.L., Rosa, A., Sabidussi, G., Turgeon, J. (ed.) Theory and Practice of Combinatorics, Volume 60 of North-Holland Mathematics Studies, pp 9 \u2013 12. North-Holland (1982). https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304020808734844"},{"key":"653_CR2","doi-asserted-by":"publisher","unstructured":"Biedl, T., Chimani, M., Derka, M., Mutzel, P.: Crossing number for graphs with bounded pathwidth. In: ISAAC\u00a0\u201907, LIPIcs, pp. 13:1\u201313:13 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.13","DOI":"10.4230\/LIPIcs.ISAAC.2017.13"},{"key":"653_CR3","doi-asserted-by":"publisher","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, 443\u2013459 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"653_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"653_CR5","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"issue":"3","key":"653_CR6","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/j.jctb.2006.06.003","volume":"97","author":"D Bokal","year":"2007","unstructured":"Bokal, D.: On the crossing numbers of cartesian products with paths. J. Comb. Theory Ser. B 97(3), 381\u2013384 (2007)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"653_CR7","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/s00454-012-9440-6","volume":"49","author":"S Cabello","year":"2013","unstructured":"Cabello, S.: Hardness of approximation for crossing number. Discrete Comput. Geom. 49(2), 348\u2013358 (2013)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"653_CR8","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/s00453-009-9357-5","volume":"60","author":"S Cabello","year":"2011","unstructured":"Cabello, S., Mohar, B.: Crossing number and weighted crossing number of near-planar graphs. Algorithmica 60(3), 484\u2013504 (2011)","journal-title":"Algorithmica"},{"key":"653_CR9","first-page":"1","volume":"33","author":"M Chimani","year":"2016","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P.: A tighter insertion-based approximation of the crossing number. J. Comb. Optim. 33, 1\u201343 (2016)","journal-title":"J. Comb. Optim."},{"key":"653_CR10","doi-asserted-by":"publisher","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P.: Inserting multiple edges into a planar graph. In: SoCG 2016, LIPIcs, pp. 30:1\u201330:15 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2016.30","DOI":"10.4230\/LIPIcs.SoCG.2016.30"},{"key":"653_CR11","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1016\/j.ejc.2011.09.009","volume":"33","author":"M Chimani","year":"2012","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P., Mutzel, P.: Vertex insertion approximates the crossing number for apex graphs. Eur. J. Comb. 33, 326\u2013335 (2012)","journal-title":"Eur. J. Comb."},{"key":"653_CR12","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: An algorithm for the graph crossing number problem. In: STOC\u00a0\u201911, pp. 303\u2013312. ACM (2011)","DOI":"10.1145\/1993636.1993678"},{"issue":"1","key":"653_CR13","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"1","key":"653_CR14","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/S0895480104442741","volume":"20","author":"E de Klerk","year":"2006","unstructured":"de Klerk, E., Maharry, J., Pasechnik, D.V., Richter, R.B., Salazar, G.: Improved bounds for the crossing numbers of $$K_{m, n}$$ and $$K_n$$. SIAM J. Discrete Math. 20(1), 189\u2013202 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"653_CR15","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H de Fraysseix","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41\u201351 (1990)","journal-title":"Combinatorica"},{"key":"653_CR16","doi-asserted-by":"crossref","unstructured":"Fox, J., Pach, J., Suk, A.: Approximating the rectilinear crossing number. In: GD 2016, LNCS 9801, pp. 413\u2013426. Springer (2016)","DOI":"10.1007\/978-3-319-50106-2_32"},{"key":"653_CR17","doi-asserted-by":"crossref","unstructured":"Gitler, I., Hlin\u011bn\u00fd, P., Leanos, J., Salazar, G.: The crossing number of a projective graph is quadratic in the face-width. Electron. J. Comb 15(1), #R46 (2008)","DOI":"10.37236\/770"},{"issue":"2","key":"653_CR18","doi-asserted-by":"publisher","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. Comput. Syst. Sci. 68(2), 285\u2013302 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"653_CR19","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/S0095-8956(03)00037-6","volume":"88","author":"P Hlin\u011bn\u00fd","year":"2003","unstructured":"Hlin\u011bn\u00fd, P.: Crossing-number critical graphs have bounded path-width. J. Comb. Theory Ser. B 88(2), 347\u2013367 (2003)","journal-title":"J. Comb. Theory Ser. B"},{"key":"653_CR20","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P., Chimani, M.: Approximating the crossing number of graphs embeddable in any orientable surface. In: SODA\u00a0\u201910, pp. 918\u2013927 (2010)","DOI":"10.1137\/1.9781611973075.74"},{"key":"653_CR21","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P., Salazar, G.: Approximating the crossing number of toroidal graphs. In: ISAAC\u00a0\u201907, LNCS 4835, pp. 148\u2013159. Springer (2007)","DOI":"10.1007\/978-3-540-77120-3_15"},{"key":"653_CR22","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.-I., Reed, B.: Computing crossing number in linear time. In: STOC \u201907, pp. 382\u2013390 (2007)","DOI":"10.1145\/1250790.1250848"},{"issue":"4","key":"653_CR23","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0021-9800(70)80087-4","volume":"9","author":"DJ Kleitman","year":"1970","unstructured":"Kleitman, D.J.: The crossing number of $${K}_{5, n}$$. J. Comb. Theory 9(4), 315\u2013323 (1970)","journal-title":"J. Comb. Theory"},{"issue":"3","key":"653_CR24","doi-asserted-by":"publisher","first-page":"571","DOI":"10.7151\/dmgt.1684","volume":"33","author":"M Kle\u0161\u010d","year":"2013","unstructured":"Kle\u0161\u010d, M., Petrillov\u00e1, J.: The crossing numbers of products of path with graphs of order six. Discuss. Math. Graph Theory 33(3), 571\u2013582 (2013)","journal-title":"Discuss. Math. Graph Theory"},{"key":"653_CR25","volume-title":"Treewidth, Computations and Approximations. LNCS 842","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS 842. Springer, Berlin (1994)"},{"issue":"2","key":"653_CR26","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1002\/jgt.20249","volume":"56","author":"S Pan","year":"2007","unstructured":"Pan, S., Richter, R.B.: The crossing number of $${K}_{11}$$ is 100. J. Graph Theory 56(2), 128\u2013134 (2007)","journal-title":"J. Graph Theory"},{"issue":"2","key":"653_CR27","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s003730200028","volume":"18","author":"RB Richter","year":"2002","unstructured":"Richter, R.B., Salazar, G.: The crossing number of $${P}({N},3)$$. Graphs Comb. 18(2), 381\u2013394 (2002)","journal-title":"Graphs Comb."},{"key":"653_CR28","volume-title":"Crossing Numbers of Graphs","author":"M Schaefer","year":"2017","unstructured":"Schaefer, M.: Crossing Numbers of Graphs. CRC Press, Boca Raton (2017)"},{"key":"653_CR29","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: ACM-SIAM Symposium on Discrete Algorithms (SODA \u201990), pp. 138\u2013148 (1990)"},{"key":"653_CR30","unstructured":"Singer, D.A.: The rectilinear crossing number of certain graphs (1971). http:\/\/www.cwru.edu\/artsci\/math\/singer\/publish\/Rectilinear_crossings.pdf"},{"key":"653_CR31","doi-asserted-by":"crossref","DOI":"10.1201\/b15385","volume-title":"Handbook of Graph Drawing and Visualization","author":"R Tamassia","year":"2013","unstructured":"Tamassia, R.: Handbook of Graph Drawing and Visualization. CRC Press, Boca Raton (2013)"},{"key":"653_CR32","unstructured":"Vrt\u2019o, I.: Crossing numbers of graphs: a bibliography (2014). ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf"},{"key":"653_CR33","first-page":"117","volume":"13","author":"DR Wood","year":"2007","unstructured":"Wood, D.R., Telle, J.A.: Planar decompositions and the crossing number of graphs with an excluded minor. N. Y. J. Math. 13, 117\u2013146 (2007)","journal-title":"N. Y. J. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00653-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00653-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00653-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T21:18:21Z","timestamp":1610486301000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00653-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,13]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["653"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00653-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,1,13]]},"assertion":[{"value":"9 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}