{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:51:05Z","timestamp":1767016265835,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031222023"},{"type":"electronic","value":"9783031222030"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-22203-0_16","type":"book-chapter","created":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T08:04:02Z","timestamp":1674029042000},"page":"219-231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Quasiplanar Graphs, String Graphs, and\u00a0the\u00a0Erd\u0151s-Gallai Problem"],"prefix":"10.1007","author":[{"given":"Jacob","family":"Fox","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Suk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,19]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00454-009-9143-9","volume":"41","author":"E Ackerman","year":"2009","unstructured":"Ackerman, E.: On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discrete Comput. Geom. 41, 365\u2013375 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-981-15-6533-5_3","volume-title":"Beyond Planar Graphs","author":"E Ackerman","year":"2020","unstructured":"Ackerman, E.: Quasi-planar graphs. In: Hong, S.-H., Tokuyama, T. (eds.) Beyond Planar Graphs, pp. 31\u201345. Springer, Singapore (2020). https:\/\/doi.org\/10.1007\/978-981-15-6533-5_3"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. J. Comb. Theory, Ser. A 114(3), 563\u2013571 (2007)","DOI":"10.1016\/j.jcta.2006.08.002"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01196127","volume":"17","author":"P Agarwal","year":"1997","unstructured":"Agarwal, P., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica 17, 1\u20139 (1997)","journal-title":"Combinatorica"},{"key":"16_CR5","unstructured":"Brass, P., Moser, W.O.J., Pach, J.: Research problems in discrete geometry. Springer (2005)"},{"key":"16_CR6","unstructured":"Burling, J.: On coloring problems of families of polytopes. (Ph.D. thesis), University of Colorado, Boulder 1(5) (1965)"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1112\/blms.12447","volume":"53","author":"J Davies","year":"2021","unstructured":"Davies, J., McCarty, R.: Circle graphs are quadratically $$\\chi $$ -bounded. Bull. London Math. Soc. 53, 673\u2013679 (2021)","journal-title":"Bull. London Math. Soc."},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Davis, J.: Improved bounds for colouring circle graphs. Preprint, arXiv:2107.03585 (2021)","DOI":"10.1090\/proc\/16044"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.jctb.2014.06.006","volume":"109","author":"A Dudek","year":"2014","unstructured":"Dudek, A., Retter, T., R\u00f6dl, V.: On generalized ramsey numbers of erdos and rogers. J. Combin. Theory Ser. B 109, 213\u2013227 (2014)","journal-title":"J. Combin. Theory Ser. B"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s00493-011-2626-3","volume":"31","author":"A Dudek","year":"2011","unstructured":"Dudek, A., R\u00f6dl, V.: On $$k_s$$-free subgraphs in $$k_{s+k}$$-free graphs and vertex folkman numbers. Combinatorica 31, 39\u201353 (2011)","journal-title":"Combinatorica"},{"key":"16_CR11","unstructured":"Erd\u0151s, P., Gallai, T.: On the minimal number of vertices representing the edges of a graph. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl. 6, 181\u2013203 (1961)"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"702","DOI":"10.4153\/CJM-1962-060-4","volume":"14","author":"P Erd\u0151s","year":"1962","unstructured":"Erd\u0151s, P., Rogers, C.A.: The construction of certain graphs. Canad. J. Math. 14, 702\u2013707 (1962)","journal-title":"Canad. J. Math."},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1016\/j.aim.2008.06.002","volume":"219","author":"J Fox","year":"2008","unstructured":"Fox, J., Pach, J.: Separator theorems and tur\u00e1n-type results for planar intersection graphs. Adv. Math. 219, 1070\u20131080 (2008)","journal-title":"Adv. Math."},{"key":"16_CR14","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. Combin. Probab. Comput. 19, 371\u2013390 (2010)","journal-title":"Combin. Probab. Comput."},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1016\/j.ejc.2011.09.021","volume":"33","author":"J Fox","year":"2012","unstructured":"Fox, J., Pach, J.: Coloring $$k_k$$-free intersection graphs of geometric objects in the plane. European J. Combin. 33, 853\u2013866 (2012)","journal-title":"European J. Combin."},{"key":"16_CR16","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, 1381\u20131401 (2012)","journal-title":"Adv. Math."},{"key":"16_CR17","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. Combin. Probab. Comput. 23, 66\u201374 (2014)","journal-title":"Combin. Probab. Comput."},{"key":"16_CR18","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, 161\u2013166 (1985)","journal-title":"Discrete Math."},{"key":"16_CR19","first-page":"1","volume":"3","author":"O Janzer","year":"2020","unstructured":"Janzer, O., Gowers, W.T.: Improved bounds for the erdos-rogers function. Adv. Comb. 3, 1\u201327 (2020)","journal-title":"Adv. Comb."},{"key":"16_CR20","unstructured":"Kostochka, A.: O verkhnikh otsenkakh khromaticheskogo chisla grafov (on upper bounds for the chromatic number of graphs). In: Dementyev, V.T. (ed.) Modeli i metody optimizacii, Akad. Nauk SSSR SO 10, pp. 204\u2013226 (1988)"},{"key":"16_CR21","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, 299\u2013305 (1997)","journal-title":"Discrete Math."},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1017\/S0963548300001243","volume":"3","author":"M Krivelevich","year":"1994","unstructured":"Krivelevich, M.: $$k_s$$-free graphs without large $$k_r$$-free subgraphs. Combin. Probab. Comput. 3, 349\u2013354 (1994)","journal-title":"Combin. Probab. Comput."},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/rsa.3240070204","volume":"7","author":"M Krivelevich","year":"1995","unstructured":"Krivelevich, M.: Bounding ramsey numbers through large deviation inequalities. Random Struct. Algorithms 7, 145\u2013155 (1995)","journal-title":"Random Struct. Algorithms"},{"key":"16_CR24","unstructured":"Lee, J.: Separators in region intersection graphs. ITCS 7, 1:1\u20131:8 (2017). Full version: arXiv:1608.01612"},{"key":"16_CR25","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R Lipton","year":"1979","unstructured":"Lipton, R., Rose, D., Tarjan, R.: Generalized nested dissections. SIAM J. Numer. Anal. 16, 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"16_CR26","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, 429\u2013439 (2000)","journal-title":"Graphs Combin."},{"key":"16_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-540-44400-8_24","volume-title":"Discrete and Computational Geometry","author":"J Pach","year":"2003","unstructured":"Pach, J., Radoi\u010di\u0107, R., T\u00f3th, G.: Relaxing planarity for topological graphs. In: Akiyama, J., Kano, M. (eds.) JCDCG 2002. LNCS, vol. 2866, pp. 221\u2013232. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-44400-8_24"},{"key":"16_CR28","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. Combin. Theory Ser. B 105, 6\u201310 (2014)","journal-title":"J. Combin. Theory Ser. B"},{"key":"16_CR29","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1007\/s00454-018-0031-z","volume":"61","author":"A Rok","year":"2019","unstructured":"Rok, A., Walczak, B.: Coloring curves that cross a fixed curve. Discrete Comput. Geom. 61, 830\u2013851 (2019)","journal-title":"Discrete Comput. Geom."},{"key":"16_CR30","doi-asserted-by":"publisher","first-page":"2181","DOI":"10.1137\/17M1157374","volume":"13","author":"A Rok","year":"2019","unstructured":"Rok, A., Walczak, B.: Outerstring graphs are $$\\chi $$-bounded. SIAM J. Discrete Math. 13, 2181\u20132199 (2019)","journal-title":"SIAM J. Discrete Math."},{"key":"16_CR31","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/rsa.20035","volume":"26","author":"B Sudakov","year":"2005","unstructured":"Sudakov, B.: Large $$k_r$$-free subgraphs in $$k_s$$-free graphs and some other ramsey-type problems. Random Struct. Algorithms 26, 253\u2013265 (2005)","journal-title":"Random Struct. Algorithms"},{"key":"16_CR32","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, 487\u2013505 (2014)","journal-title":"Combinatorica"},{"key":"16_CR33","unstructured":"Tomon, I.: String graphs have the erdos-hajnal property. arXiv preprint. arXiv:2002.10350 (2020)"},{"key":"16_CR34","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/PL00009364","volume":"19","author":"P Valtr","year":"1998","unstructured":"Valtr, P.: On geometric graphs with no $$k$$ pairwise parallel edges. Discrete Comput. Geom. 19, 461\u2013469 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"16_CR35","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s00454-014-9645-y","volume":"53","author":"B Walczak","year":"2015","unstructured":"Walczak, B.: Triangle-free geometric intersection graphs with no large independent sets. Discrete Comput. Geom. 53, 221\u2013225 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"16_CR36","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s00493-013-2845-x","volume":"33","author":"G Wolfovitz","year":"2013","unstructured":"Wolfovitz, G.: $$k_4$$-free graphs without large induced triangle-free subgraphs. Combinatorica 33, 623\u2013631 (2013)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22203-0_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T07:04:46Z","timestamp":1704351886000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22203-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031222023","9783031222030"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22203-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"19 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"GD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Graph Drawing and Network Visualization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tokyo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/graphdrawing.github.io\/gd2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"70","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.01","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7.03","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}