{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:12:17Z","timestamp":1761621137416,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T00:00:00Z","timestamp":1370217600000},"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":["SIGACT News"],"published-print":{"date-parts":[[2013,6,3]]},"abstract":"<jats:p>This column is devoted to maximum (respectively, maximum weight) independent set problems in geometric intersection graphs. We illustrate with one example in each class:<\/jats:p>\n          <jats:p>\n            (I) The following question was asked by T. Rado in 1928: What is the largest number\n            <jats:italic>c<\/jats:italic>\n            such that, for any finite set\n            <jats:italic>F<\/jats:italic>\n            of axis-parallel squares in the plane, there exists an independent subset\n            <jats:italic>I<\/jats:italic>\n            \u2286\n            <jats:italic>F<\/jats:italic>\n            of pairwise disjoint squares with total area at least\n            <jats:italic>c<\/jats:italic>\n            times the union area of the squares.\n          <\/jats:p>\n          <jats:p>\n            (II) The following question was asked by Erd\u00f6s in 1983: What is the largest number\n            <jats:italic>H<\/jats:italic>\n            =\n            <jats:italic>H<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) with the property that every set of\n            <jats:italic>n<\/jats:italic>\n            non-overlapping unit disks in the plane has an independent subset with at least\n            <jats:italic>H<\/jats:italic>\n            members?\n          <\/jats:p>","DOI":"10.1145\/2491533.2491550","type":"journal-article","created":{"date-parts":[[2013,6,5]],"date-time":"2013-06-05T12:09:34Z","timestamp":1370434174000},"page":"80-87","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Computational geometry column 56"],"prefix":"10.1145","volume":"44","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Wisconsin--Milwaukee, USA"}]},{"given":"Minghui","family":"Jiang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Utah State University, Logan, USA"}]}],"member":"320","published-online":{"date-parts":[[2013,6,3]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"61","volume":"21","author":"Ajtai M.","year":"1973","journal-title":"Astronomiques et Physiques"},{"key":"e_1_2_1_2_1","first-page":"105","volume":"20","author":"Bereg S.","year":"2010","journal-title":"Maximum area independent set in disk intersection graphs, International Journal of Computational Geometry & Applications"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9298-z"},{"volume-title":"Research Problems in Discrete Geometry","year":"2005","author":"Bras P.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00294-8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0963-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009381"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2616915.2616942"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462385"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402676"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/2372148"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719802","volume-title":"Topics in Intersection Graph Theory","author":"McKee T. A.","year":"1999"},{"key":"e_1_2_1_15_1","unstructured":"H. Minkowski Geometrie der Zahlen Leipzig 1896 (reprinted in 2009).  H. Minkowski Geometrie der Zahlen Leipzig 1896 (reprinted in 2009)."},{"key":"e_1_2_1_16_1","first-page":"29","volume":"6","author":"Norlander G.","year":"1958","journal-title":"Nordisk Matematisk Tidskrift"},{"key":"e_1_2_1_17_1","unstructured":"J. Pach and G. T\u00f3th On the independence number of coin graphs Geombinatorics 6 (1996) 30--33.  J. Pach and G. T\u00f3th On the independence number of coin graphs Geombinatorics 6 (1996) 30--33."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(85)90106-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-51.3.232"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-53.4.243"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-43.1.127"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-11-1-228-229"},{"key":"e_1_2_1_23_1","first-page":"871","volume":"26","author":"Sokolin A.","year":"1940","journal-title":"Sci. U.R.S.S. (N.S.)"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2897-y"},{"key":"e_1_2_1_25_1","first-page":"141","volume":"5","author":"Zalgaller V. A.","year":"1960","journal-title":"Matem. Prosveskcheric"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491533.2491550","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2491533.2491550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:50Z","timestamp":1750231730000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491533.2491550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,3]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6,3]]}},"alternative-id":["10.1145\/2491533.2491550"],"URL":"https:\/\/doi.org\/10.1145\/2491533.2491550","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2013,6,3]]},"assertion":[{"value":"2013-06-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}