{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:01Z","timestamp":1740109561529,"version":"3.37.3"},"reference-count":8,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,12,18]],"date-time":"2020-12-18T00:00:00Z","timestamp":1608249600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,12,18]],"date-time":"2020-12-18T00:00:00Z","timestamp":1608249600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hungarian Ministry for Innovation and Technology","award":["NKFIH-843-10\/2019"],"award-info":[{"award-number":["NKFIH-843-10\/2019"]}]},{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","award":["K-131529"],"award-info":[{"award-number":["K-131529"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"crossref","award":["KKP-133864"],"award-info":[{"award-number":["KKP-133864"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The crossing number of a graph <jats:italic>G<\/jats:italic> is the minimum number of edge crossings over all drawings of <jats:italic>G<\/jats:italic> in the plane. A graph <jats:italic>G<\/jats:italic> is <jats:italic>k<\/jats:italic>-crossing-critical if its crossing number is at least\u00a0<jats:italic>k<\/jats:italic>, but if we remove any edge of <jats:italic>G<\/jats:italic>, its crossing number drops below\u00a0<jats:italic>k<\/jats:italic>. There are examples of <jats:italic>k<\/jats:italic>-crossing-critical graphs that do not have drawings with exactly <jats:italic>k<\/jats:italic> crossings. Richter and Thomassen proved in 1993 that if <jats:italic>G<\/jats:italic> is <jats:italic>k<\/jats:italic>-crossing-critical, then its crossing number is at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$2.5\\, k+16$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2.5<\/mml:mn>\n                    <mml:mspace\/>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>16<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We improve this bound to <jats:inline-formula><jats:alternatives><jats:tex-math>$$2k+8\\sqrt{k}+47$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>8<\/mml:mn>\n                    <mml:msqrt>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>47<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00454-020-00264-2","type":"journal-article","created":{"date-parts":[[2020,12,18]],"date-time":"2020-12-18T14:03:16Z","timestamp":1608300196000},"page":"595-604","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improvement on the Crossing Number of Crossing-Critical Graphs"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8474-487X","authenticated-orcid":false,"given":"J\u00e1nos","family":"Bar\u00e1t","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1751-6911","authenticated-orcid":false,"given":"G\u00e9za","family":"T\u00f3th","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,12,18]]},"reference":[{"key":"264_CR1","doi-asserted-by":"publisher","first-page":"#\u00a0101574","DOI":"10.1016\/j.comgeo.2019.101574","volume":"85","author":"E Ackerman","year":"2019","unstructured":"Ackerman, E.: On topological graphs with at most four crossings per edge. Comput. Geom. 85, #\u00a0101574 (2019)","journal-title":"Comput. Geom."},{"key":"264_CR2","unstructured":"Bokal, D., Dvo\u0159\u00e1k, Z., Hlin\u011bn\u00fd, P., Leanos, J., Mohar, B., Wiedera, T.: Bounded degree conjecture holds precisely for $$c$$-crossing-critical graphs with $$c\\le 12$$. In: 35th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 129, #\u00a014. Leibniz-Zent. Inform., Wadern (2019)"},{"key":"264_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.aam.2015.10.003","volume":"74","author":"D Bokal","year":"2016","unstructured":"Bokal, D., Oporowski, B., Richter, R.B., Salazar, G.: Characterizing $$2$$-crossing-critical graphs. Adv. Appl. Math. 74, 23\u2013208 (2016)","journal-title":"Adv. Appl. Math."},{"issue":"1","key":"264_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.jctb.2007.03.005","volume":"98","author":"J Fox","year":"2008","unstructured":"Fox, J., T\u00f3th, C.D.: On the decay of crossing numbers. J. Comb. Theory Ser. B 98(1), 33\u201342 (2008)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"264_CR5","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1002\/jgt.20172","volume":"53","author":"M Lomel\u00ed","year":"2006","unstructured":"Lomel\u00ed, M., Salazar, G.: Nearly light cycles in embedded graphs and crossing-critical graphs. J. Graph Theory 53(2), 151\u2013156 (2006)","journal-title":"J. Graph Theory"},{"issue":"2","key":"264_CR6","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1006\/jctb.1993.1038","volume":"58","author":"RB Richter","year":"1993","unstructured":"Richter, R.B., Thomassen, C.: Minimal graphs with crossing number at least $$k$$. J. Comb. Theory Ser. B 58(2), 217\u2013224 (1993)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"264_CR7","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1006\/jctb.1999.1943","volume":"79","author":"G Salazar","year":"2000","unstructured":"Salazar, G.: On a crossing number result of Richter and Thomassen. J. Comb. Theory Ser. B 79(1), 98\u201399 (2000)","journal-title":"J. Comb. Theory Ser. B"},{"key":"264_CR8","volume-title":"Crossing Numbers of Graphs. Discrete Mathematics and its Applications (Boca Raton)","author":"M Schaefer","year":"2018","unstructured":"Schaefer, M.: Crossing Numbers of Graphs. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton (2018)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00264-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00264-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00264-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T22:11:55Z","timestamp":1644099115000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00264-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,18]]},"references-count":8,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["264"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00264-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2020,12,18]]},"assertion":[{"value":"28 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}