{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T00:34:07Z","timestamp":1772843647152,"version":"3.50.1"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T00:00:00Z","timestamp":1580774400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T00:00:00Z","timestamp":1580774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["635\/16"],"award-info":[{"award-number":["635\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006245","name":"Ministry of Science and Technology, Israel","doi-asserted-by":"publisher","award":["Shulamit Aloni Postdoctoral Fellowship"],"award-info":[{"award-number":["Shulamit Aloni Postdoctoral Fellowship"]}],"id":[{"id":"10.13039\/501100006245","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Kreitman Foundation","award":["Postdoctoral Fellowship"],"award-info":[{"award-number":["Postdoctoral Fellowship"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00454-020-00179-y","type":"journal-article","created":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T19:02:39Z","timestamp":1580842959000},"page":"1337-1372","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Conflict-Free Coloring of String Graphs"],"prefix":"10.1007","volume":"65","author":[{"given":"Chaya","family":"Keller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandre","family":"Rok","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shakhar","family":"Smorodinsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,4]]},"reference":[{"key":"179_CR1","doi-asserted-by":"crossref","unstructured":"Abel, Z., Alvarez, V., Demaine, E.D., Fekete, S.P., Gour, A., Hesterberg, A., Keldenich, P., Scheffer, C.: Three colors suffice: conflict-free coloring of planar graphs. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1951\u20131963. SIAM, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.127"},{"issue":"6","key":"179_CR2","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1142\/S0218195908002775","volume":"18","author":"N Alon","year":"2008","unstructured":"Alon, N., Smorodinsky, S.: Conflict-free colorings of shallow discs. Int. J. Comput. Geom. Appl. 18(6), 599\u2013604 (2008)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"179_CR3","volume-title":"The Probabilistic Method. 2nd edn. Wiley-Interscience Series in Discrete Mathematics and Optimization","author":"N Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. 2nd edn. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (2000)"},{"key":"179_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.tcs.2016.03.007","volume":"654","author":"K Balas","year":"2016","unstructured":"Balas, K., T\u00f3th, C.D.: On the number of anchored rectangle packings for a planar point set. Theoret. Comput. Sci. 654, 143\u2013154 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"11","key":"179_CR5","doi-asserted-by":"publisher","first-page":"1607","DOI":"10.1073\/pnas.45.11.1607","volume":"45","author":"S Benzer","year":"1959","unstructured":"Benzer, S.: On the topology of the genetic fine structure. Proc. Natl. Acad. Sci. USA 45(11), 1607\u20131620 (1959)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"179_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set. In: Proceedings of the 28th Annual Symposuim on Computational Geometry (SoCG \u201912), pp. 293\u2013302. ACM (2012)","DOI":"10.1145\/2261250.2261293"},{"key":"179_CR7","unstructured":"Chaplick, S., Ueckerdt, T.: Planar graphs as VPG-graphs. In: Didimo, W., Patrignani, M. (eds.) Graph Drawing. Lecture Notes in Computer Science, 7704, pp. 174\u2013186 Springer, Heidelberg (2013)"},{"key":"179_CR8","unstructured":"Cheilaris, P.: Conflict-Free Coloring. Ph.D. Thesis, City University of New York (2009)"},{"issue":"5","key":"179_CR9","first-page":"545","volume":"36","author":"K Chen","year":"2006","unstructured":"Chen, K., Fiat, A., Kaplan, H., Levy, M., Matou\u0161ek, J., Mossel, E., Pach, J., Sharir, M., Smorodinsky, S., Wagner, U., Welzl, E.: Online conflict-free coloring for intervals. SIAM J. Comput. 36(5), 545\u2013554 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"179_CR10","doi-asserted-by":"publisher","first-page":"16.1","DOI":"10.1145\/1497290.1497292","volume":"5","author":"K Chen","year":"2009","unstructured":"Chen, K., Kaplan, H., Sharir, M.: Online conflict free coloring for halfplanes, congruent disks, and axis-parallel rectangles. ACM Trans. Algorithms 5(2), 16.1\u201316.24 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"179_CR11","first-page":"135","volume":"23","author":"C Chojanski","year":"1934","unstructured":"Chojanski, C.: \u00dcber wesentlich unpl\u00e4ttbare Kurven im dreidimensionalen Raume. Fund. Math. 23(1), 135\u2013142 (1934)","journal-title":"Fund. Math."},{"key":"179_CR12","unstructured":"Chudnovsky, M., Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings (2015). https:\/\/web.math.princeton.edu\/~pds\/papers\/strings\/paper.pdf"},{"issue":"1","key":"179_CR13","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/0095-8956(76)90022-8","volume":"21","author":"G Ehrlich","year":"1976","unstructured":"Ehrlich, G., Even, S., Tarjan, R.E.: Intersection graphs of curves in the plane. J. Comb. Theory Ser. B 21(1), 8\u201320 (1976)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"179_CR14","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1137\/S0097539702431840","volume":"33","author":"G Even","year":"2003","unstructured":"Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33(1), 94\u2013136 (2003)","journal-title":"SIAM J. Comput."},{"key":"179_CR15","unstructured":"Fekete, S.P., Keldenich, P.: Conflict-free coloring of intersection graphs. In: Okamoto, Y., Tokuyama, T. (eds.) Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017). LIPIcs. Leibniz International Proceedings in Informatics, vol. 92, pp. 31:1\u201331:12. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.31"},{"key":"179_CR16","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.dam.2016.01.028","volume":"206","author":"S Felsner","year":"2016","unstructured":"Felsner, S., Knauer, K., Mertzios, G.B., Ueckerdt, T.: Intersection graphs of L-shapes and segments in the plane. Discrete Appl. Math. 206, 48\u201355 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"179_CR17","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1017\/S0963548309990459","volume":"19","author":"J Fox","year":"2010","unstructured":"Fox, J., Pach, J.: A separator theorem for string graphs and its applications. Comb. Probab. Comput. 19(3), 371\u2013390 (2010)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"179_CR18","doi-asserted-by":"publisher","first-page":"1381","DOI":"10.1016\/j.aim.2012.03.011","volume":"230","author":"J Fox","year":"2012","unstructured":"Fox, J., Pach, J.: String graphs and incomparability graphs. Adv. Math. 230(3), 1381\u20131401 (2012)","journal-title":"Adv. Math."},{"issue":"1","key":"179_CR19","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1017\/S0963548313000412","volume":"23","author":"J Fox","year":"2014","unstructured":"Fox, J., Pach, J.: Applications of a new separator theorem for string graphs. Comb. Probab. Comput. 23(1), 66\u201374 (2014)","journal-title":"Comb. Probab. Comput."},{"key":"179_CR20","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.tcs.2014.11.029","volume":"566","author":"L Gargano","year":"2015","unstructured":"Gargano, L., Rescigno, A.A.: Complexity of conflict-free colorings of graphs. Theor. Comput. Sci. 566, 39\u201349 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"179_CR21","doi-asserted-by":"crossref","unstructured":"Gibson, M., Varadarajan, K.R.: Decomposing coverings and the planar sensor cover problem. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 159\u2013168. IEEE, Los Alamitos (2009)","DOI":"10.1109\/FOCS.2009.54"},{"issue":"3","key":"179_CR22","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1017\/S0963548313000540","volume":"23","author":"R Glebov","year":"2014","unstructured":"Glebov, R., Szab\u00f3, T., Tardos, G.: Conflict-free colouring of graphs. Comb. Probab. Comput. 23(3), 434\u2013448 (2014)","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"179_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0012-365X(85)90044-5","volume":"55","author":"A Gy\u00e1rf\u00e1s","year":"1985","unstructured":"Gy\u00e1rf\u00e1s, A.: On the chromatic number of multiple interval graphs and overlap graphs. Discrete Math. 55(2), 161\u2013166 (1985)","journal-title":"Discrete Math."},{"issue":"1","key":"179_CR24","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00454-005-1162-6","volume":"34","author":"S Har-Peled","year":"2005","unstructured":"Har-Peled, S., Smorodinsky, S.: Conflict-free coloring of points and simple regions in the plane. Discrete Comput. Geom. 34(1), 47\u201370 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"179_CR25","doi-asserted-by":"crossref","unstructured":"Horev, E., Krakovski, R., Smorodinsky, S.: Conflict-free coloring made stronger. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010). Lecture Notes in Computer Science, vol. 6139, pp. 105\u2013117. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13731-0_11"},{"key":"179_CR26","doi-asserted-by":"crossref","unstructured":"Keller, C., Smorodinsky, S.: Conflict-free coloring of intersection graphs of geometric objects. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 2397\u20132411. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.154"},{"key":"179_CR27","doi-asserted-by":"publisher","unstructured":"Keller, C., Smorodinsky, S.: Conflict-free coloring of intersection graphs of geometric objects. Discrete Comput. Geom. https:\/\/doi.org\/10.1007\/s00454-019-00097-8","DOI":"10.1007\/s00454-019-00097-8"},{"key":"179_CR28","unstructured":"Keszegh, B.: Weak conflict-free colorings of point sets and simple regions. In: Proceedings of the 19th Annual Canadian Conference on Computational Geometry (CCCG 2007), pp. 97\u2013100. (2007)"},{"key":"179_CR29","unstructured":"Keszegh, B.: Combinatorial and Computational Problems About Points in the Plane. Ph.D. Thesis, Central European University (2009)"},{"key":"179_CR30","unstructured":"Keszegh, B.: Coloring intersection hypergraphs of pseudo-disks. In: Speckmann, B., T\u00f3th, C.D. (eds.) Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018). LIPIcs. Leibniz International Proceedings in Informatics, vol.\u00a099, pp. 52:1\u201352:15. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2018)"},{"key":"179_CR31","unstructured":"Kostochka, A.V.: Upper bounds on the chromatic number of graphs. Trudy Inst. Mat. (Novosibirsk) 10(Modeli i Metody Optim.), 204\u2013226 (1988) (in Russian)"},{"issue":"1\u20133","key":"179_CR32","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0012-365X(96)00344-5","volume":"163","author":"A Kostochka","year":"1997","unstructured":"Kostochka, A., Kratochv\u00edl, J.: Covering and coloring polygon-circle graphs. Discrete Math. 163(1\u20133), 299\u2013305 (1997)","journal-title":"Discrete Math."},{"issue":"1","key":"179_CR33","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1006\/eujc.1997.0151","volume":"19","author":"AV Kostochka","year":"1998","unstructured":"Kostochka, A.V., Ne\u0161et\u0159il, J.: Coloring relatives of intervals on the plane. I. Chromatic number versus girth. Eur. J. Comb. 19(1), 103\u2013110 (1998)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"179_CR34","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/eujc.2000.0433","volume":"23","author":"AV Kostochka","year":"1998","unstructured":"Kostochka, A.V., Ne\u0161et\u0159il, J.: Colouring relatives of intervals on the plane, II: Intervals and rays in two directions. Eur. J. Comb. 23(1), 37\u201341 (1998)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"179_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0095-8956(91)90050-T","volume":"53","author":"J Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: String graphs requiring exponential representations. J. Comb. Theory Ser. B 53(1), 1\u20134 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"179_CR36","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s00454-014-9640-3","volume":"53","author":"T Krawczyk","year":"2015","unstructured":"Krawczyk, T., Pawlik, A., Walczak, B.: Coloring triangle-free rectangle overlap graphs with $$O(\\log \\log n)$$ colors. Discrete Comput. Geom. 53(1), 199\u2013220 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"179_CR37","doi-asserted-by":"crossref","unstructured":"Krawczyk, T., Walczak, B.: Coloring relatives of interval overlap graphs via on-line games. In: Proceedings of the 41st International on Colloquium Automata, Languages, and Programming (ICALP 2014), Part I. Lecture Notes in Computer Science, vol. 8572, pp. 738\u2013750. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-43948-7_61"},{"issue":"6","key":"179_CR38","doi-asserted-by":"publisher","first-page":"1139","DOI":"10.1007\/s00493-016-3414-x","volume":"37","author":"T Krawczyk","year":"2017","unstructured":"Krawczyk, T., Walczak, B.: On-line approach to off-line coloring problems on graphs with geometric representations. Combinatorica 37(6), 1139\u20131179 (2017)","journal-title":"Combinatorica"},{"issue":"2","key":"179_CR39","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00454-014-9614-5","volume":"52","author":"M Laso\u0144","year":"2014","unstructured":"Laso\u0144, M., Micek, P., Pawlik, A., Walczak, B.: Coloring intersection graphs of arc-connected sets in the plane. Discrete Comput. Geom. 52(2), 399\u2013415 (2014)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"179_CR40","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1017\/S0963548313000400","volume":"23","author":"J Matou\u0161ek","year":"2014","unstructured":"Matou\u0161ek, J.: Near-optimal separators in string graphs. Combin. Probab. Comput. 23(1), 135\u2013139 (2014)","journal-title":"Combin. Probab. Comput."},{"issue":"1","key":"179_CR41","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0012-365X(95)00316-O","volume":"154","author":"S McGuinness","year":"1996","unstructured":"McGuinness, S.: On bounding the chromatic number of L-graphs. Discrete Math. 154(1), 179\u2013187 (1996)","journal-title":"Discrete Math."},{"issue":"4","key":"179_CR42","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/PL00007228","volume":"16","author":"S McGuinness","year":"2000","unstructured":"McGuinness, S.: Colouring arcwise connected sets in the plane I. Graphs Combin. 16(4), 429\u2013439 (2000)","journal-title":"Graphs Combin."},{"issue":"5","key":"179_CR43","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1017\/S0963548309990290","volume":"18","author":"J Pach","year":"2009","unstructured":"Pach, J., Tardos, G.: Conflict-free colourings of graphs and hypergraphs. Comb. Probab. Comput. 18(5), 819\u2013834 (2009)","journal-title":"Comb. Probab. Comput."},{"key":"179_CR44","doi-asserted-by":"crossref","unstructured":"Pach, J., Tardos, G., T\u00f3th, G.: Indecomposable coverings. In: The China\u2013Japan Joint Conference on Discrete Geometry, Combinatorics, and Graph Theory (CJCDGCGT 2005). Lecture Notes in Computer Sceince, vol. 4381, pp. 135\u2013148. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-70666-3_15"},{"issue":"4","key":"179_CR45","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s00454-002-2891-4","volume":"28","author":"J Pach","year":"2002","unstructured":"Pach, J., T\u00f3th, G.: Recognizing string graphs is decidable. Discrete Comput. Geom. 28(4), 593\u2013606 (2002)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"179_CR46","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.comgeo.2008.08.002","volume":"42","author":"J Pach","year":"2009","unstructured":"Pach, J., T\u00f3th, G.: Decomposition of multiple coverings into many parts. Comput. Geom. 42(2), 127\u2013133 (2009)","journal-title":"Comput. Geom."},{"key":"179_CR47","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.jctb.2013.11.001","volume":"105","author":"A Pawlik","year":"2014","unstructured":"Pawlik, A., Kozik, J., Krawczyk, T., Laso\u0144, M., Micek, P., Trotter, W., Walczak, B.: Triangle-free intersection graphs of line segments with large chromatic number. J. Comb. Theory, Ser. B 105, 6\u201310 (2014)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"179_CR48","doi-asserted-by":"crossref","unstructured":"Rok, A., Walczak, B.: Outerstring graphs are $$\\chi $$-bounded. In: Proceedings of the 30th Annual Symposium on Computational Geometry (SOCG\u201914), pp. 136\u2013143. ACM, New York (2014)","DOI":"10.1145\/2582112.2582115"},{"key":"179_CR49","unstructured":"Rok, A., Walczak, B.: Coloring curves that cross a fixed curve. In: Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917). Leibniz International Proceedings in Informatics, vol. 77, pp. 56:1\u201356:15. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2017)"},{"key":"179_CR50","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Recognizing string graphs in NP. J. Comput. System Sci., special issue of STOC\u20192002 67(2), 593\u2013606 (2003)"},{"key":"179_CR51","volume-title":"Algorithms for VLSI Physical Design Automation","author":"NA Sherwani","year":"1999","unstructured":"Sherwani, N.A.: Algorithms for VLSI Physical Design Automation, 3rd edn. Springer, Boston (1999)","edition":"3"},{"key":"179_CR52","unstructured":"Smorodinsky, S.: Combinatorial Problems in Computational Geometry. Ph.D. Thesis, Tel-Aviv University (2003)"},{"key":"179_CR53","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/050642368","volume":"21","author":"S Smorodinsky","year":"2007","unstructured":"Smorodinsky, S.: On the chromatic number of some geometric hypergraphs. SIAM J. Discrete Math. 21, 676\u2013687 (2007)","journal-title":"SIAM J. Discrete Math."},{"key":"179_CR54","unstructured":"Smorodinsky, S.: Conflict-free coloring and its applications. CoRR arXiv:1005.3616 (2010)"},{"key":"179_CR55","first-page":"331","volume-title":"Geometry\u2014Intuitive, Discrete, and Convex. Bolyai Society Mathematical Studies","author":"S Smorodinsky","year":"2013","unstructured":"Smorodinsky, S.: Conflict-free coloring and its applications. In: B\u00e1r\u00e1ny, I., et al. (eds.) Geometry\u2014Intuitive, Discrete, and Convex. Bolyai Society Mathematical Studies, vol. 24, pp. 331\u2013389. Springer, Berlin (2013)"},{"issue":"4","key":"179_CR56","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s00493-014-2942-5","volume":"34","author":"A Suk","year":"2014","unstructured":"Suk, A.: Coloring intersection graphs of $$x$$-monotone curves in the plane. Combinatorica 34(4), 487\u2013505 (2014)","journal-title":"Combinatorica"},{"key":"179_CR57","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0021-9800(70)80007-2","volume":"8","author":"WT Tutte","year":"1970","unstructured":"Tutte, W.T.: Toward a theory of crossing numbers. J. Comb. Theory 8, 45\u201353 (1970)","journal-title":"J. Comb. Theory"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00179-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00179-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00179-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T15:28:23Z","timestamp":1619537303000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00179-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,4]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["179"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00179-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,4]]},"assertion":[{"value":"23 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}