{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T03:48:55Z","timestamp":1774583335038,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188854","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"574-586","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs"],"prefix":"10.1145","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[{"name":"Utrecht University, Netherlands \/ Eindhoven University of Technology, Netherlands"}]},{"given":"S\u00e1ndor","family":"Kisfaludi-Bak","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Hungarian Academy of Sciences, Hungary"}]},{"given":"Tom C. van der","family":"Zanden","sequence":"additional","affiliation":[{"name":"Utrecht University, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.001"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/120891241"},{"key":"e_1_3_2_2_3_1","volume-title":"Thilikos","author":"Baste Julien","year":"2018","unstructured":"Julien Baste and Dimitrios M . Thilikos . 2018 . Contraction-Bidimensionality of Geometric Intersection Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Daniel Lokshtanov and Naomi Nishimura (Eds.), Vol. 89 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany , 5:1\u20135:13. Julien Baste and Dimitrios M. Thilikos. 2018. Contraction-Bidimensionality of Geometric Intersection Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Daniel Lokshtanov and Naomi Nishimura (Eds.), Vol. 89. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 5:1\u20135:13."},{"key":"e_1_3_2_2_4_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry, SoCG 2017 (LIPCS)","volume":"77","author":"Bir\u00f3 Csaba","year":"2017","unstructured":"Csaba Bir\u00f3 , \u00c9douard Bonnet , D\u00e1niel Marx , Tillmann Miltzow , and Pawe\u0142 Rz\u0105\u017cewski . 2017 . Fine-Grained Complexity of Coloring Unit Disks and Balls . In Proceedings of the 33rd International Symposium on Computational Geometry, SoCG 2017 (LIPCS) , Vol. 77 . Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 18:1\u201318:16. Csaba Bir\u00f3, \u00c9douard Bonnet, D\u00e1niel Marx, Tillmann Miltzow, and Pawe\u0142 Rz\u0105\u017cewski. 2017. Fine-Grained Complexity of Coloring Unit Disks and Balls. In Proceedings of the 33rd International Symposium on Computational Geometry, SoCG 2017 (LIPCS), Vol. 77. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 18:1\u201318:16."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00014-X"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_3_2_2_8_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V Fomin , \u0141ukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V Fomin, \u0141ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188854"},{"key":"e_1_3_2_2_10_1","volume-title":"12th International Symposium on Parameterized and Exact Computation (IPEC 2017) (Leibniz International Proceedings in Informatics (LIPIcs))","author":"de Berg Mark","unstructured":"Mark de Berg , S\u00e1ndor Kisfaludi-Bak , and Gerhard Woeginger . 2018. The Dominating Set Problem in Geometric Intersection Graphs . In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) (Leibniz International Proceedings in Informatics (LIPIcs)) , Daniel Lokshtanov and Naomi Nishimura (Eds.), Vol. 89 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany , 14:1\u201314:12. Mark de Berg, S\u00e1ndor Kisfaludi-Bak, and Gerhard Woeginger. 2018. The Dominating Set Problem in Geometric Intersection Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Daniel Lokshtanov and Naomi Nishimura (Eds.), Vol. 89. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 14:1\u201314:12."},{"key":"e_1_3_2_2_11_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 (LIPICS)","volume":"80","author":"Fomin Fedor V.","year":"2017","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Fahad Panolan , Saket Saurabh , and Meirav Zehavi . 2017 . Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 (LIPICS) , Vol. 80 . Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 65:1\u201365:15. LIPIcs.ICALP. 2017.65 Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. 2017. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 (LIPICS), Vol. 80. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 65:1\u201365:15. LIPIcs.ICALP.2017.65"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095240"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.05.003"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000260"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_60"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_2_17_1","volume-title":"Kang and Tobias M\u00fcller","author":"Ross","year":"2012","unstructured":"Ross J. Kang and Tobias M\u00fcller . 2012 . Sphere and Dot Product Representations of Graphs. Discrete & Computational Geometry 47, 3 (2012), 548\u2013568. Ross J. Kang and Tobias M\u00fcller. 2012. Sphere and Dot Product Representations of Graphs. Discrete & Computational Geometry 47, 3 (2012), 548\u2013568."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57586-5_31"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_4"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582124"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.08.006"},{"key":"e_1_3_2_2_25_1","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS 1998. IEEE Computer Society, 232\u2013243","author":"Warren","unstructured":"Warren D. Smith and Nicholas C. Wormald. 1998. Geometric Separator Theorems & Applications . In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS 1998. IEEE Computer Society, 232\u2013243 . Warren D. Smith and Nicholas C. Wormald. 1998. Geometric Separator Theorems & Applications. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS 1998. IEEE Computer Society, 232\u2013243."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188854","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188854"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":25,"alternative-id":["10.1145\/3188745.3188854","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188854","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}