{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T09:43:24Z","timestamp":1773395004856,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,27]],"date-time":"2020-09-27T00:00:00Z","timestamp":1601164800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,27]],"date-time":"2020-09-27T00:00:00Z","timestamp":1601164800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s00453-020-00769-5","type":"journal-article","created":{"date-parts":[[2020,9,27]],"date-time":"2020-09-27T14:02:38Z","timestamp":1601215358000},"page":"641-666","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On Orthogonally Guarding Orthogonal Polygons with Bounded Treewidth"],"prefix":"10.1007","volume":"83","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[]},{"given":"Saeed","family":"Mehrabi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,27]]},"reference":[{"key":"769_CR1","unstructured":"Biedl, T.,\u00a0Mehrabi, S.: On r-guarding thin orthogonal polygons. In: 27th International Symposium on Algorithms and Computation (ISAAC 2016), Vol.\u00a064 of LIPIcs, pp. 17:1\u201317:13 (D2016)"},{"key":"769_CR2","unstructured":"Biedl, T.,\u00a0Mehrabi, S.: On guarding orthogonal polygons with bounded treewidth. In: Canadian Conference on Computational Geometry (CCCG 2017), Ottawa, Ontario (2017)"},{"key":"769_CR3","series-title":"The International Series of Monographs on Computer Science","volume-title":"Art Gallery Theorems and Algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. The International Series of Monographs on Computer Science. Oxford University Press, New York (1987)"},{"key":"769_CR4","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. J. Combin. Theory, Ser. B 18, 39\u201341 (1975)","journal-title":"J. Combin. Theory, Ser. B"},{"issue":"2","key":"769_CR5","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"DT Lee","year":"1986","unstructured":"Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32(2), 276\u2013282 (1986)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"769_CR6","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1002\/malq.19950410212","volume":"41","author":"D Schuchardt","year":"1995","unstructured":"Schuchardt, D., Hecker, H.-D.: Two NP-hard art-gallery problems for ortho-polygons. Math. Logic Q. 41(2), 261\u2013267 (1995)","journal-title":"Math. Logic Q."},{"issue":"3","key":"769_CR7","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/s00453-012-9653-3","volume":"66","author":"E Krohn","year":"2013","unstructured":"Krohn, E., Nilsson, B.J.: Approximate guarding of monotone and rectilinear polygons. Algorithmica 66(3), 564\u2013594 (2013)","journal-title":"Algorithmica"},{"key":"769_CR8","doi-asserted-by":"crossref","unstructured":"Tom\u00e1s, A.P.: Guarding thin orthogonal polygons is hard. In: Proceedings of Fundamentals of Computation Theory (FCT 2013), Vol. 8070 of LNCS, pp. 305\u2013316 (2013)","DOI":"10.1007\/978-3-642-40164-0_29"},{"issue":"1","key":"769_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","volume":"31","author":"S Eidenbenz","year":"2001","unstructured":"Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31(1), 79\u2013113 (2001)","journal-title":"Algorithmica"},{"issue":"6","key":"769_CR10","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.dam.2009.12.004","volume":"158","author":"SK Ghosh","year":"2010","unstructured":"Ghosh, S.K.: Approximation algorithms for art gallery problems in polygons. Discret. Appl. Math. 158(6), 718\u2013722 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"769_CR11","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1142\/S0218195911003639","volume":"21","author":"MJ Katz","year":"2011","unstructured":"Katz, M.J., Morgenstern, G.: Guarding orthogonal art galleries with sliding cameras. Int. J. Comput. Geom. Appl. 21(2), 241\u2013250 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"769_CR12","doi-asserted-by":"crossref","unstructured":"Durocher, S., Mehrabi, S.: Guarding orthogonal art galleries using sliding cameras: algorithmic and hardness results. In: Proceedings of Mathematical Foundations of Computer Science (MFCS 2013), Vol. 8087 of LNCS, pp. 314\u2013324 (2013)","DOI":"10.1007\/978-3-642-40313-2_29"},{"key":"769_CR13","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.comgeo.2017.04.001","volume":"65","author":"S Durocher","year":"2017","unstructured":"Durocher, S., Filtser, O., Fraser, R., Mehrabi, A.D., Mehrabi, S.: Guarding orthogonal art galleries with sliding cameras. Comput. Geom. 65, 12\u201326 (2017)","journal-title":"Comput. Geom."},{"key":"769_CR14","unstructured":"Mehrabi, S.: Geometric optimization problems on orthogonal polygons: hardness results and approximation algorithms, Ph.D. thesis, University of Manitoba, Winnipeg, Canada (August 2015)"},{"key":"769_CR15","doi-asserted-by":"crossref","unstructured":"Franzblau, D.S., Kleitman, D.J.: An algorithm for constructing regions with rectangles: independence and minimum generating sets for collections of intervals. In: Proceedings of the ACM Symposium on Theory of Computing (STOC 1984), pp. 167\u2013174 (1984)","DOI":"10.1145\/800057.808678"},{"issue":"3","key":"769_CR16","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/0402033","volume":"2","author":"R Motwani","year":"1989","unstructured":"Motwani, R., Raghunathan, A., Saran, H.: Perfect graphs and orthogonally convex covers. SIAM J. Discret. Math. 2(3), 371\u2013392 (1989)","journal-title":"SIAM J. Discret. Math."},{"issue":"5","key":"769_CR17","doi-asserted-by":"publisher","first-page":"1316","DOI":"10.1137\/100791506","volume":"40","author":"J King","year":"2011","unstructured":"King, J., Krohn, E.: Terrain guarding is np-hard. SIAM J. Comput. 40(5), 1316\u20131339 (2011)","journal-title":"SIAM J. Comput."},{"key":"769_CR18","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.comgeo.2019.07.004","volume":"84","author":"O Daescu","year":"2019","unstructured":"Daescu, O., Friedrichs, S., Malik, H., Polishchuk, V., Schmidt, C.: Altitude terrain guarding and guarding uni-monotone polygons. Comput. Geom. 84, 22\u201335 (2019)","journal-title":"Comput. Geom."},{"key":"769_CR19","unstructured":"Durocher, S., Li, P.C., Mehrabi, S.: Guarding orthogonal terrains. In: Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Ontario, Canada, August 10\u201312, 2015, Queen\u2019s University, Ontario, Canada (2015)"},{"issue":"2","key":"769_CR20","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1142\/S0218195907002264","volume":"17","author":"C Worman","year":"2007","unstructured":"Worman, C., Keil, J.M.: Polygon decomposition and the orthogonal art gallery problem. Int. J. Comput. Geom. Appl. 17(2), 105\u2013138 (2007)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"769_CR21","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/s00454-012-9429-1","volume":"48","author":"TC Biedl","year":"2012","unstructured":"Biedl, T.C., Irfan, M.T., Iwerks, J., Kim, J., Mitchell, J.S.B.: The art gallery theorem for polyominoes. Discret. Comput. Geom. 48(3), 711\u2013720 (2012)","journal-title":"Discret. Comput. Geom."},{"issue":"6\u20137","key":"769_CR22","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.comgeo.2008.11.004","volume":"42","author":"EM Arkin","year":"2009","unstructured":"Arkin, E.M., Fekete, S.P., Islam, K., Meijer, H., Mitchell, J.S.B., Rodr\u00edguez, Y.N., Polishchuk, V., Rappaport, D., Xiao, H.: Not being (super)thin or solid is hard: a study of grid hamiltonicity. Comput. Geom. 42(6\u20137), 582\u2013605 (2009)","journal-title":"Comput. Geom."},{"key":"769_CR23","doi-asserted-by":"crossref","unstructured":"Keil, J.M.: Minimally covering a horizontally convex orthogonal polygon. In: Proceedings of the ACM Symposium on Computational Geometry (SoCG 1986), pp. 43\u201351 (1986)","DOI":"10.1145\/10515.10520"},{"issue":"2","key":"769_CR24","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1142\/S021819591250001X","volume":"22","author":"A Lingas","year":"2012","unstructured":"Lingas, A., Wasylewicz, A., Zylinski, P.: Linear-time 3-approximation algorithm for the r-star covering problem. Int. J. Comput. Geom. Appl. 22(2), 103\u2013142 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"769_CR25","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(89)90043-3","volume":"39","author":"J Culberson","year":"1989","unstructured":"Culberson, J., Reckhow, R.A.: Orthogonally convex coverings of orthogonal polygons without holes. J. Comput. Syst. Sci. 39(2), 166\u2013204 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"769_CR26","doi-asserted-by":"crossref","unstructured":"Palios, L., Tzimas, P.: Minimum r-star cover of class-3 orthogonal polygons. In: Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2014), Vol. 8986 of LNCS, Springer, pp. 286\u2013297 (2015)","DOI":"10.1007\/978-3-319-19315-1_25"},{"key":"769_CR27","doi-asserted-by":"crossref","unstructured":"Motwani, R.,\u00a0Raghunathan, A.,\u00a0Saran, H.: Covering orthogonal polygons with star polygons: the perfect graph approach. In: ACM Symposium on Computational Geometry (SoCG 1988), pp. 211\u2013223 (1988)","DOI":"10.1145\/73393.73415"},{"issue":"1","key":"769_CR28","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0022-0000(90)90017-F","volume":"40","author":"R Motwani","year":"1990","unstructured":"Motwani, R., Raghunathan, A., Saran, H.: Covering orthogonal polygons with star polygons: the perfect graph approach. J. Comput. Syst. Sci. 40(1), 19\u201348 (1990)","journal-title":"J. Comput. Syst. Sci."},{"key":"769_CR29","doi-asserted-by":"crossref","unstructured":"Biedl, T.,\u00a0Mehrabi, S.: Grid obstacle representations with connections to staircase guarding. In: Graph Drawing and Network Visualization (GD\u201917), LNCS, Springer-Verlag, (2017), To appear","DOI":"10.1007\/978-3-319-73915-1_7"},{"key":"769_CR30","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0925-7721(93)90013-V","volume":"2","author":"L Gewali","year":"1992","unstructured":"Gewali, L., Ntafos, S.C.: Covering grids and orthogonal polygons with periscope guards. Comput. Geom. 2, 309\u2013334 (1992)","journal-title":"Comput. Geom."},{"key":"769_CR31","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF00147413","volume":"37","author":"T Shermer","year":"1991","unstructured":"Shermer, T.: Covering and guarding polygons using $$L_k$$-sets. Geom. Dedicata. 37, 183\u2013203 (1991)","journal-title":"Geom. Dedicata."},{"key":"769_CR32","doi-asserted-by":"crossref","unstructured":"Biedl, T., Chan, T.M.,\u00a0Lee, S.,\u00a0Mehrabi, S.,\u00a0Montecchiani, F.,\u00a0Vosoughpour, H.: On guarding orthogonal polygons with sliding cameras. In: International Conference and Workshops on Algorithms and Computation (WALCOM 2017), Vol. 10167 of LNCS, Springer, pp. 54\u201365 (2017)","DOI":"10.1007\/978-3-319-53925-6_5"},{"key":"769_CR33","doi-asserted-by":"crossref","unstructured":"Bandyapadhyay, S., Roy, A.B.: Effectiveness of local search for art gallery problems. In: proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS 2017), St. John\u2019s, NL, Canada, pp. 49\u201360 (2017)","DOI":"10.1007\/978-3-319-62127-2_5"},{"issue":"3","key":"769_CR34","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1145\/321958.321964","volume":"23","author":"PJ Slater","year":"1976","unstructured":"Slater, P.J.: R-domination in graphs. J. ACM 23(3), 446\u2013450 (1976)","journal-title":"J. ACM"},{"issue":"1","key":"769_CR35","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"769_CR36","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: On the expression of graph properties in some fragments of monadic second-order logic. In: DIAMCS Workshop on Descriptive Complexity and Finite Models, American Mathematical Society, pp. 33\u201357 (1997)","DOI":"10.1090\/dimacs\/031\/02"},{"issue":"1","key":"769_CR37","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"5","key":"769_CR38","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discret. Comput. Geom. 6(5), 485\u2013524 (1991)","journal-title":"Discret. Comput. Geom."},{"key":"769_CR39","doi-asserted-by":"crossref","unstructured":"Kammer, F., Tholey, T.: Approximate tree decompositions of planar graphs in linear time. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 683\u2013698 (2012)","DOI":"10.1137\/1.9781611973099.57"},{"issue":"2","key":"769_CR40","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"769_CR41","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"769_CR42","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae 15(2), 307\u2013309 (1974)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"769_CR43","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BF02086606","volume":"16","author":"G Kant","year":"1996","unstructured":"Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16, 4\u201332 (1996)","journal-title":"Algorithmica"},{"issue":"1","key":"769_CR44","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B Baker","year":"1994","unstructured":"Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"1","key":"769_CR45","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1051\/ro:2002005","volume":"36","author":"S Kovaleva","year":"2002","unstructured":"Kovaleva, S., Spieksma, F.C.R.: Primal-dual approximation algorithms for a packing-covering pair of problems. RAIRO - Oper. Res. 36(1), 53\u201371 (2002)","journal-title":"RAIRO - Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00769-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00769-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00769-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,26]],"date-time":"2021-09-26T23:28:36Z","timestamp":1632698916000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00769-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,27]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["769"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00769-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,27]]},"assertion":[{"value":"2 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}