{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:36Z","timestamp":1750307016724,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,6,17]],"date-time":"2012-06-17T00:00:00Z","timestamp":1339891200000},"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":[[2012,6,17]]},"DOI":"10.1145\/2261250.2261311","type":"proceedings-article","created":{"date-parts":[[2012,6,20]],"date-time":"2012-06-20T13:33:01Z","timestamp":1340199181000},"page":"405-414","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["String graphs and incomparability graphs"],"prefix":"10.1145","author":[{"given":"Jacob","family":"Fox","sequence":"first","affiliation":[{"name":"MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,6,17]]},"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.1145\/1542362.1542430"},{"key":"e_1_3_2_1_3_1","first-page":"9","volume-title":"Theory and Practice of Combinatorics","author":"Ajtai M.","year":"1982","unstructured":"M. Ajtai , V. Chv\u00e1tal , M. Newborn , and E. Szemer\u00e9di , Crossing-free subgraphs , in: Theory and Practice of Combinatorics , vol. 60 , Mathematical Studies , North- Holland ,Amsterdam, 1982 , pp. 9 -- 12 . M. Ajtai, V. Chv\u00e1tal, M. Newborn, and E. Szemer\u00e9di,Crossing-free subgraphs, in: Theory and Practice of Combinatorics, vol. 60, Mathematical Studies, North-Holland,Amsterdam, 1982, pp. 9--12."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.45.11.1607"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.170.941"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2465-x"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"R. P. Dilworth Annals of Math. 51 (1950) 161--166.  R. P. Dilworth Annals of Math. 51 (1950) 161--166.","DOI":"10.2307\/1969503"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90022-8"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"e_1_3_2_1_10_1","first-page":"463","article-title":"A combinatorial problem ingeometry","volume":"2","author":"Erdos P.","year":"1935","unstructured":"P. Erdos and G. Szekeres , A combinatorial problem ingeometry , Compositio Math. 2 ( 1935 ), 463 -- 470 . P. Erdos and G. Szekeres, A combinatorial problem ingeometry, Compositio Math. 2 (1935), 463--470.","journal-title":"Compositio Math."},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/1377676.1377735"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdq087"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-010-0056-3"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.03.005"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"e_1_3_2_1_17_1","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M.","year":"1980","unstructured":"M. Golumbic , Algorithmic Graph Theory and Perfect Graphs , Academic Press , New York , 1980 . M. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90019-5"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1959.11989408"},{"key":"e_1_3_2_1_20_1","first-page":"1195","volume-title":"Combinatorics","author":"Graham R. L.","year":"1978","unstructured":"R. L. Graham , Problem , in: Combinatorics , Vol. II (A. Hajnal and V. T. S\u00f3s, eds.), North-Holland, Amsterdam , 1978 , p. 1195 . R. L. Graham, Problem, in: Combinatorics, Vol. II (A. Hajnal and V. T. S\u00f3s, eds.), North-Holland, Amsterdam, 1978, p. 1195."},{"key":"e_1_3_2_1_21_1","first-page":"1","article-title":"On the dimension of orders","volume":"4","author":"Hiraguchi T.","unstructured":"T. Hiraguchi , On the dimension of orders , Sci. Rep. Kanazawa Univ. Vol. 4 , 1 -- 20 . T. Hiraguchi, On the dimension of orders, Sci. Rep. Kanazawa Univ. Vol. 4, 1--20.","journal-title":"Sci. Rep. Kanazawa Univ."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009317"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1975-0369090-9"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.09.002"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90090-7"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90091-W"},{"key":"e_1_3_2_1_28_1","volume-title":"String graphs. Rozpravy Ceskoslovenske Akad. Ved Rada Mat. Pr'irod. Ved 96","author":"Kratochv\u00edl J.","year":"1986","unstructured":"J. Kratochv\u00edl , M. Goljan , and P. Kucera , String graphs. Rozpravy Ceskoslovenske Akad. Ved Rada Mat. Pr'irod. Ved 96 ( 1986 ), 96 pp. J. Kratochv\u00edl, M. Goljan, and P. Kucera, String graphs. Rozpravy Ceskoslovenske Akad. Ved Rada Mat. Pr'irod. Ved 96 (1986), 96 pp."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90050-T"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.06.054"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/26.2.132"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744433"},{"key":"e_1_3_2_1_33_1","volume-title":"Selected Topics in Graph Theory","author":"Lov\u00e1sz L.","year":"1983","unstructured":"L. Lov\u00e1sz , Perfect graphs , in: Selected Topics in Graph Theory , vol. 2 , Academic Press , London , 1983 , 55--87. L. Lov\u00e1sz, Perfect graphs, in: Selected Topics in Graph Theory, vol. 2, Academic Press, London, 1983, 55--87."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-005-0616-1"},{"key":"e_1_3_2_1_35_1","volume-title":"Relaxing planarity for topological graphs, Discrete and Computational Geometry","author":"Pach J.","year":"2003","unstructured":"J. Pach , R. Radoici\u0107 , and G. T\u00f3th , Relaxing planarity for topological 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. Radoici\u0107, and G. T\u00f3th, Relaxing planarity for topological graphs, Discrete and Computational Geometry (J.Akiyama, M. Kano, eds.), Lecture Notes in Computer Science 2866 Springer-Verlag, Berlin, 2003, 221--232."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2891-4"},{"key":"e_1_3_2_1_37_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_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0032-z"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00045-X"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.002"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01713.x"},{"key":"e_1_3_2_1_42_1","volume-title":"Johns Hopkins Series in the Mathematical Sciences","author":"Trotter W. T.","year":"1992","unstructured":"W. T. Trotter , Combinatorics and Partially Ordered Sets. Dimension Theory , Johns Hopkins Series in the Mathematical Sciences , Johns Hopkins University Press , Baltimore, MD , 1992 . W. T. Trotter, Combinatorics and Partially Ordered Sets. Dimension Theory, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992."}],"event":{"name":"SoCG '12: Symposium on Computational Geometry 2012","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chapel Hill North Carolina USA","acronym":"SoCG '12"},"container-title":["Proceedings of the twenty-eighth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2261250.2261311","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2261250.2261311","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:08Z","timestamp":1750236548000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2261250.2261311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,17]]},"references-count":42,"alternative-id":["10.1145\/2261250.2261311","10.1145\/2261250"],"URL":"https:\/\/doi.org\/10.1145\/2261250.2261311","relation":{},"subject":[],"published":{"date-parts":[[2012,6,17]]},"assertion":[{"value":"2012-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}