{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:38:48Z","timestamp":1787326728577,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100007397","name":"Charles University","doi-asserted-by":"crossref","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}],"id":[{"id":"10.13039\/100007397","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007397","name":"Charles University","doi-asserted-by":"crossref","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}],"id":[{"id":"10.13039\/100007397","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["Y1329"],"award-info":[{"award-number":["Y1329"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"publisher","award":["10.47379\/ICT22029"],"award-info":[{"award-number":["10.47379\/ICT22029"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["810115"],"award-info":[{"award-number":["810115"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["21-32817S"],"award-info":[{"award-number":["21-32817S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["21-32817S"],"award-info":[{"award-number":["21-32817S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["Wo 754\/11-1"],"award-info":[{"award-number":["Wo 754\/11-1"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["DACH"],"award-info":[{"award-number":["DACH"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021E-171681"],"award-info":[{"award-number":["200021E-171681"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V007793\/1"],"award-info":[{"award-number":["EP\/V007793\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>An obstacle representation of a graph [Formula: see text] consists of a set of pairwise disjoint simply connected closed regions and a one-to-one mapping of the vertices of [Formula: see text] to points such that two vertices are adjacent in [Formula: see text] if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each [Formula: see text]-vertex graph is [Formula: see text] [M. Balko, J. Cibulka, and P. Valtr, Discrete Comput.\u00a0Geom., 59 (2018), pp.\u00a0143\u2013164] and that there are [Formula: see text]-vertex graphs whose obstacle number is [Formula: see text] [V. Dujmovi\u0107 and P. Morin, Electron.\u00a0J.\u00a0Combin., 22 (2015), 3.1]. We improve this lower bound to [Formula: see text] for simple polygons and to [Formula: see text] for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of [Formula: see text]-vertex graphs with bounded obstacle number, solving a conjecture by Dujmovi\u0107 and Morin. We also show that if the drawing of some [Formula: see text]-vertex graph is given as part of the input, then for some drawings [Formula: see text] obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph [Formula: see text] is fixed-parameter tractable in the vertex cover number of [Formula: see text]. Second, we show that, given a graph [Formula: see text] and a simple polygon [Formula: see text], it is NP-hard to decide whether [Formula: see text] admits an obstacle representation using [Formula: see text] as the only obstacle.<\/jats:p>","DOI":"10.1137\/23m1585088","type":"journal-article","created":{"date-parts":[[2024,5,20]],"date-time":"2024-05-20T04:42:52Z","timestamp":1716180172000},"page":"1537-1565","source":"Crossref","is-referenced-by-count":3,"title":["Bounding and Computing Obstacle Numbers of Graphs"],"prefix":"10.1137","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9688-9489","authenticated-orcid":true,"given":"Martin","family":"Balko","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3501-4608","authenticated-orcid":true,"given":"Steven","family":"Chaplick","sequence":"additional","affiliation":[{"name":"Maastricht University, 6200 MD Maastricht, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7762-8045","authenticated-orcid":true,"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, Technische Universit\u00e4t Wien, Vienna, Austria."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4671-9822","authenticated-orcid":true,"given":"Siddharth","family":"Gupta","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Information Systems, BITS Pilani Goa Campus, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5307-7106","authenticated-orcid":true,"given":"Michael","family":"Hoffmann","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Switzerland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3102-4166","authenticated-orcid":true,"given":"Pavel","family":"Valtr","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5872-718X","authenticated-orcid":true,"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,5,20]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195916600037"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9233-8"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9919-2"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9831-1"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50106-2_23"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.37236\/4373"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9366-4"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22203-0_31"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/0204035"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.042"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-73915-1_6"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187696"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58043-7_6"},{"key":"ref15","unstructured":"M. P. Johnson and D. Sar\u0131\u00f6z, Representing a planar straight-line graph using few obstacles, in Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG), 2014, pp. 95\u201399, http:\/\/www.cccg.ca\/proceedings\/2014\/papers\/paper14.pdf."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55611-7"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.37236\/2380"},{"key":"ref18","first-page":"264","volume":"30","author":"Ramsey F. P.","year":"1929","journal-title":"Proc. London Math. Soc. (2)"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80004-5"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80005-7"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90044-4"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1585088","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:35:17Z","timestamp":1787322917000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1585088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,20]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1137\/23M1585088"],"URL":"https:\/\/doi.org\/10.1137\/23m1585088","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,20]]}}}