{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:47Z","timestamp":1750307807401,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,6,9]],"date-time":"2008-06-09T00:00:00Z","timestamp":1212969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2008,6,9]]},"DOI":"10.1145\/1377676.1377735","type":"proceedings-article","created":{"date-parts":[[2008,6,10]],"date-time":"2008-06-10T14:13:22Z","timestamp":1213107202000},"page":"346-354","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Coloring\n            <i>\n              k\n              <sub>k<\/sub>\n            <\/i>\n            -free intersection graphs of geometric objects in the plane"],"prefix":"10.1145","author":[{"given":"Jacob","family":"Fox","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[{"name":"City College of New York, New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2008,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137895"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/647547.728593"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00028-5"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1143176.1646569"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2168005.2168087"},{"key":"e_1_3_2_1_6_1","volume-title":"Crossing families. Combinatorica14","author":"Aronov B.","year":"1994","unstructured":"B. Aronov , P. Erd\u00f6s , W. Goddard , D. Kleitman , M. Klugerman , J. Pach , and L. J. Schulman , Crossing families. Combinatorica14 ( 1994 ), 127--134.]] B. Aronov, P. Erd\u00f6s, W. Goddard, D. Kleitman, M. Klugerman, J.Pach, and L. J. Schulman, Crossing families. Combinatorica14 (1994), 127--134.]]"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10607"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in realalgebraic geometry","author":"Basu S.","year":"2006","unstructured":"S. Basu , R. Pollack , and M.-F. Roy , Algorithms in realalgebraic geometry . Second edition. Algorithms and Computation in Mathematics 10, Springer-Verlag , Berlin, 2006 .]] S. Basu, R. Pollack, and M.-F. Roy, Algorithms in realalgebraic geometry. Second edition. Algorithms and Computation in Mathematics 10, Springer-Verlag, Berlin, 2006.]]"},{"key":"e_1_3_2_1_9_1","first-page":"436","article-title":"Improved approximation algorithms for rectangle tiling and packing, in: Proc. 12th ACM-SIAM Sympos","volume":"427","author":"Berman P.","year":"2001","unstructured":"P. Berman , B. DasGupta , S. Muthukrishnan , and S. Ramaswami , Improved approximation algorithms for rectangle tiling and packing, in: Proc. 12th ACM-SIAM Sympos . Discrete Algorithms , 2001 , 427 -- 436 .]] P. Berman, B. DasGupta, S. Muthukrishnan, and S. Ramaswami, Improved approximation algorithms for rectangle tiling and packing, in: Proc. 12th ACM-SIAM Sympos. Discrete Algorithms, 2001, 427--436.]]","journal-title":"Discrete Algorithms"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00294-8"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-006-9043-z"},{"key":"e_1_3_2_1_12_1","unstructured":"J. Fox and J. Pach Separator theorems and Tur\u00e1n-type results forplanar intersection graphs Advances in Mathematics submitted.]]  J. Fox and J. Pach Separator theorems and Tur\u00e1n-type results forplanar intersection graphs Advances in Mathematics submitted.]]"},{"key":"e_1_3_2_1_13_1","unstructured":"J. Fox and J. Pach String graphs and incomparability graphs inpreparation.]]  J. Fox and J. Pach String graphs and incomparability graphs inpreparation.]]"},{"volume-title":"Bolyai Soc. Mathematical Studies, J. Bolyai Mathematical Soc.","author":"Fox J.","key":"e_1_3_2_1_14_1","unstructured":"J. Fox and J. Pach , Erd\u00f6s-Hajnal-type results on intersectionpatterns of geometric objects , Bolyai Soc. Mathematical Studies, J. Bolyai Mathematical Soc. , Budapest , to appear.]] J. Fox and J. Pach, Erd\u00f6s-Hajnal-type results on intersectionpatterns of geometric objects, Bolyai Soc. Mathematical Studies, J. Bolyai Mathematical Soc., Budapest, to appear.]]"},{"volume-title":"Intersection patterns of curves","author":"Fox J.","key":"e_1_3_2_1_15_1","unstructured":"J. Fox , J. Pach , and Cs. T\u00f3th , Intersection patterns of curves , J. London Mathematical Society , accepted.]] J. Fox, J. Pach, and Cs. T\u00f3th, Intersection patterns of curves, J. London Mathematical Society, accepted.]]"},{"key":"e_1_3_2_1_16_1","unstructured":"J. Fox J. Pach and Cs. T\u00f3th Tur\u00e1n-type results for partialorders and intersection graphs of convex sets Israel J.Math. submitted.]]  J. Fox J. Pach and Cs. T\u00f3th Tur\u00e1n-type results for partialorders and intersection graphs of convex sets Israel J.Math. submitted.]]"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_3_2_1_18_1","volume-title":"Computers andIntractability: A Guide to the Theory of NP--Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson , Computers andIntractability: A Guide to the Theory of NP--Completeness , Freeman ,New York, 1979 .]] M. R. Garey and D. S. Johnson, Computers andIntractability: A Guide to the Theory of NP--Completeness, Freeman,New York, 1979.]]"},{"key":"e_1_3_2_1_19_1","volume-title":"Rozpravy Ceskoslovensk\u00e9 Akad. Ved Rada Mat. Pr\u00edrod. Ved 96","author":"Goljan M.","year":"1986","unstructured":"M. Goljan , J. Kratochv\u00edl , and P. Ku\u010dera , String graphs , Rozpravy Ceskoslovensk\u00e9 Akad. Ved Rada Mat. Pr\u00edrod. Ved 96 ( 1986 ), 96 pp.]] M. Goljan, J. Kratochv\u00edl, and P. Ku\u010dera, String graphs, Rozpravy Ceskoslovensk\u00e9 Akad. Ved Rada Mat. Pr\u00edrod. Ved 96 (1986), 96 pp.]]"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90019-5"},{"key":"e_1_3_2_1_21_1","first-page":"413","article-title":"Problems from the world surrounding perfect graphs","volume":"19","author":"Gy\u00e1rf\u00e1s A.","year":"1987","unstructured":"A. Gy\u00e1rf\u00e1s , Problems from the world surrounding perfect graphs . Zastos. Mat. 19 ( 1987 ), 413 -- 441 (1988).]] A. Gy\u00e1rf\u00e1s, Problems from the world surrounding perfect graphs. Zastos. Mat. 19 (1987), 413--441 (1988).]]","journal-title":"Zastos. Mat."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90045-7"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90012-3"},{"key":"e_1_3_2_1_26_1","volume-title":"Proc. 9th ACM-SIAM Sympos. Discrete Algorithms","author":"Khanna S.","year":"1998","unstructured":"S. Khanna , S. Muthukrishnan and M. Paterson , On approximating rectangle tiling and packing , in: Proc. 9th ACM-SIAM Sympos. Discrete Algorithms , 1998 ,384--393]] S. Khanna, S. Muthukrishnan and M. Paterson, On approximating rectangle tiling and packing, in: Proc. 9th ACM-SIAM Sympos. Discrete Algorithms, 1998,384--393]]"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.37236\/1805"},{"key":"e_1_3_2_1_28_1","first-page":"141","article-title":"Kontaktprobleme der konformen Abbildung, Berichte\u00fcber die Verhandlungen der Sachsischen Akademie derWissenschaften, Leipzig","volume":"88","author":"Koebe P.","year":"1936","unstructured":"P. Koebe , Kontaktprobleme der konformen Abbildung, Berichte\u00fcber die Verhandlungen der Sachsischen Akademie derWissenschaften, Leipzig , Mathematische-Physische Klasse 88 ,( 1936 ), 141 -- 164 .]] P. Koebe, Kontaktprobleme der konformen Abbildung, Berichte\u00fcber die Verhandlungen der Sachsischen Akademie derWissenschaften, Leipzig, Mathematische-Physische Klasse 88,(1936), 141--164.]]","journal-title":"Mathematische-Physische Klasse"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.09.002"},{"key":"e_1_3_2_1_30_1","volume-title":"Towards a theory of geometric graphs, Contemp. Math., 342, Amer. Math. Soc.","author":"Kostochka A. V.","year":"2004","unstructured":"A. V. Kostochka , Coloring intersection graphs of geometric figureswith a given clique number , Towards a theory of geometric graphs, Contemp. Math., 342, Amer. Math. Soc. , Providence , RI ,( 2004 ), 127--138.]] A. V. Kostochka, Coloring intersection graphs of geometric figureswith a given clique number, Towards a theory of geometric graphs, Contemp. Math., 342, Amer. Math. Soc., Providence, RI,(2004), 127--138.]]"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0151"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.2000.0433"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/26.2.132"},{"key":"e_1_3_2_1_34_1","first-page":"1","volume-title":"Proceedings of a Conference on Theoretical Computer Science","author":"Lipton R. J.","year":"1977","unstructured":"R. J. Lipton and R. E. Tarjan , A separator theorem for planargraphs . Proceedings of a Conference on Theoretical Computer Science ( Univ. Waterloo, Waterloo, Ont. , 1977 ), pp. 1 -- 10 . Comput.Sci. Dept., Univ. Waterloo, Waterloo, Ont., 1978.]] R. J. Lipton and R. E. Tarjan, A separator theorem for planargraphs. Proceedings of a Conference on Theoretical Computer Science (Univ. Waterloo, Waterloo, Ont., 1977), pp. 1--10. Comput.Sci. Dept., Univ. Waterloo, Waterloo, Ont., 1978.]]"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)89267-9"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007228"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256294"},{"key":"e_1_3_2_1_38_1","first-page":"285","article-title":"Notes on geometric graph theory, Discrete and Computational Geometry (J.E. Goodman et al, eds.), DIMACS Series, Vol 6, Amer. Math. Soc","volume":"273","author":"Pach J.","year":"1991","unstructured":"J. Pach , Notes on geometric graph theory, Discrete and Computational Geometry (J.E. Goodman et al, eds.), DIMACS Series, Vol 6, Amer. Math. Soc ., Providence , 1991 , 273 -- 285 .]] J. Pach, Notes on geometric graph theory, Discrete and Computational Geometry (J.E. Goodman et al, eds.), DIMACS Series, Vol 6, Amer. Math. Soc., Providence, 1991, 273--285.]]","journal-title":"Providence"},{"key":"e_1_3_2_1_39_1","first-page":"232","article-title":"Relaxing planarity fortopological graphs, Discrete and Computational Geometry (J.Akiyama, M. Kano, eds.), Lecture Notes in Computer Science 2866,Springer-Verlag","volume":"221","author":"Pach J.","year":"2003","unstructured":"J. Pach , R. Radoi\u010di\u0107 , and G. T\u00f3th , Relaxing planarity fortopological graphs, Discrete and Computational Geometry (J.Akiyama, M. Kano, eds.), Lecture Notes in Computer Science 2866,Springer-Verlag , Berlin , 2003 , 221 -- 232 .]] J. Pach, R. Radoi\u010di\u0107, and G. T\u00f3th, Relaxing planarity fortopological graphs, Discrete and Computational Geometry (J.Akiyama, M. Kano, eds.), Lecture Notes in Computer Science 2866,Springer-Verlag, Berlin, 2003, 221--232.]]","journal-title":"Berlin"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/177424.177629"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574361"},{"key":"e_1_3_2_1_42_1","series-title":"Lecture Notes in Computer Science 1984","volume-title":"Graph Drawing","author":"Pach J.","year":"2000","unstructured":"J. Pach and G. T\u00f3th , Unavoidable configurations in complete topological graphs , Graph Drawing 2000 , Lecture Notes in Computer Science 1984 , Springer-Verlag , 2001, 328--337.]] J. Pach and G. T\u00f3th, Unavoidable configurations in complete topological graphs, Graph Drawing 2000, Lecture Notes in Computer Science 1984, Springer-Verlag, 2001, 328--337.]]"},{"key":"e_1_3_2_1_43_1","first-page":"150","article-title":"Comment on Fox News","volume":"15","author":"Pach J.","year":"2006","unstructured":"J. Pach and G. T\u00f3th , Comment on Fox News , Geombinatorics 15 ( 2006 ), 150 -- 154 .]] J. Pach and G. T\u00f3th, Comment on Fox News, Geombinatorics 15 (2006), 150--154.]]","journal-title":"Geombinatorics"},{"key":"e_1_3_2_1_44_1","first-page":"73","article-title":"On coloring polygon-circle graphs with clique number2","volume":"10","author":"Shmatkov R. N.","year":"2000","unstructured":"R. N. Shmatkov , On coloring polygon-circle graphs with clique number2 , Siberian Adv. Math. 10 ( 2000 ), 73 -- 86 .]] R. N. Shmatkov, On coloring polygon-circle graphs with clique number2, Siberian Adv. Math. 10 (2000), 73--86.]]","journal-title":"Siberian Adv. Math."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00143891"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796397"},{"key":"e_1_3_2_1_47_1","first-page":"436","article-title":"On a problem in extremal graph theory (in Hungarian)","volume":"48","author":"Tur\u00e1n P.","year":"1941","unstructured":"P. Tur\u00e1n , On a problem in extremal graph theory (in Hungarian) . Math. Fiz. Lapok 48 ( 1941 ), 436 -- 452 .]] P. Tur\u00e1n, On a problem in extremal graph theory (in Hungarian). Math. Fiz. Lapok 48 (1941), 436--452.]]","journal-title":"Math. Fiz. Lapok"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009364"},{"key":"e_1_3_2_1_49_1","series-title":"Lecture Notes in Computer Science","volume-title":"Graph Drawing","author":"Valtr P.","year":"1997","unstructured":"P. Valtr , Graphs drawn in the plane with no pairwise crossing edges , In G. D. Battista, editor, Graph Drawing , volume 1353 of Lecture Notes in Computer Science , 205--218, Springer , 1997 .]] P. Valtr, Graphs drawn in the plane with no pairwise crossing edges, In G. D. Battista, editor, Graph Drawing, volume 1353 of Lecture Notes in Computer Science, 205--218, Springer, 1997.]]"}],"event":{"name":"SoCG08: 24th Annual Symposium on Computational Geometry","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"College Park MD USA","acronym":"SoCG08"},"container-title":["Proceedings of the twenty-fourth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377676.1377735","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1377676.1377735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:39Z","timestamp":1750254999000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377676.1377735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,9]]},"references-count":49,"alternative-id":["10.1145\/1377676.1377735","10.1145\/1377676"],"URL":"https:\/\/doi.org\/10.1145\/1377676.1377735","relation":{},"subject":[],"published":{"date-parts":[[2008,6,9]]},"assertion":[{"value":"2008-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}