{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:30Z","timestamp":1740109590148,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FE 560\/6-1"],"award-info":[{"award-number":["FE 560\/6-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is<jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\,\\mathrm{{\\textsf{N}}{\\textsf{P}}}\\,}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mspace\/><mml:mrow><mml:mi>N<\/mml:mi><mml:mi>P<\/mml:mi><\/mml:mrow><mml:mspace\/><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be<jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\,\\mathrm{{\\textsf{N}}{\\textsf{P}}}\\,}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mspace\/><mml:mrow><mml:mi>N<\/mml:mi><mml:mi>P<\/mml:mi><\/mml:mrow><mml:mspace\/><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard, which settles an open question.<\/jats:p>","DOI":"10.1007\/s00454-022-00414-8","type":"journal-article","created":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T19:02:46Z","timestamp":1679511766000},"page":"937-980","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Combinatorial Properties and Recognition of Unit Square Visibility Graphs"],"prefix":"10.1007","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6146-8684","authenticated-orcid":false,"given":"Katrin","family":"Casel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4444-3220","authenticated-orcid":false,"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8391-235X","authenticated-orcid":false,"given":"Alexander","family":"Grigoriev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5137-1504","authenticated-orcid":false,"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sue","family":"Whitesides","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,22]]},"reference":[{"key":"414_CR1","doi-asserted-by":"crossref","unstructured":"Argyriou, E.N., Bekos, M.A., Symvonis, A.: Maximizing the total resolution of graphs. In: 18th International Symposium on Graph Drawing (Konstanz 2010). Lecture Notes in Comput. Sci., vol. 6502, pp. 62\u201367. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-18469-7_6"},{"issue":"2","key":"414_CR2","doi-asserted-by":"publisher","first-page":"569","DOI":"10.7155\/jgaa.00274","volume":"16","author":"EN Argyriou","year":"2012","unstructured":"Argyriou, E.N., Bekos, M.A., Symvonis, A.: The straight-line RAC drawing problem is NP-hard. J. Gr. Algorithms Appl. 16(2), 569\u2013597 (2012)","journal-title":"J. Gr. Algorithms Appl."},{"key":"414_CR3","doi-asserted-by":"crossref","unstructured":"Arleo, A., Binucci, C., Di Giacomo, E., Evans, W.S., Grilli,\u00a0L., Liotta,\u00a0G., Meijer,\u00a0H., Montecchiani,\u00a0F., Whitesides,\u00a0S., Wismath,\u00a0S.: Visibility representations of boxes in $$2.5$$ dimensions. In: 24th International Symposium on Graph Drawing and Network Visualization (Athens 2016). Lecture Notes in Computer Science, vol. 9801, pp. 251\u2013265. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-50106-2_20"},{"issue":"1","key":"414_CR4","doi-asserted-by":"publisher","first-page":"345","DOI":"10.7155\/jgaa.00362","volume":"19","author":"M Babbitt","year":"2015","unstructured":"Babbitt, M., Geneson, J., Khovanova, T.: On $$k$$-visibility graphs. J. Gr. Algorithms Appl. 19(1), 345\u2013360 (2015)","journal-title":"J. Gr. Algorithms Appl."},{"issue":"4","key":"414_CR5","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0020-0190(87)90173-6","volume":"25","author":"SN Bhatt","year":"1987","unstructured":"Bhatt, S.N., Cosmadakis, S.S.: The complexity of minimizing wire lengths in VLSI layouts. Inform. Process. Lett. 25(4), 263\u2013267 (1987)","journal-title":"Inform. Process. Lett."},{"key":"414_CR6","unstructured":"Biedl, Th., Liotta, G., Montecchiani, F.: On visibility representations on non-planar graphs. In: 32nd International Symposium on Computational Geometry (Boston 2016). Leibniz International Proceedings in Informatics, vol. 51, #\u00a019. Leibniz-Zent. Inform., Wadern (2016)"},{"issue":"1","key":"414_CR7","doi-asserted-by":"publisher","first-page":"89","DOI":"10.7155\/jgaa.00083","volume":"8","author":"HL Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Tel, G.: A note on rectilinearity and angular resolution. J. Gr. Algorithms Appl. 8(1), 89\u201394 (2004)","journal-title":"J. Gr. Algorithms Appl."},{"issue":"3","key":"414_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00006","volume":"2","author":"P Bose","year":"1998","unstructured":"Bose, P., Everett, H., Fekete, S.P., Houle, M.E., Lubiw, A., Meijer, H., Romanik, K., Rote, G., Shermer, T.C., Whitesides, S., Zelle, Ch.: A visibility representation for graphs in three dimensions. J. Gr. Algorithms Appl. 2(3), 1\u201316 (1998)","journal-title":"J. Gr. Algorithms Appl."},{"key":"414_CR9","unstructured":"Casel, K., Fernau, H., Grigoriev, A., Schmid, M.L., Whitesides, S.: Combinatorial properties and recognition of unit square visibility graphs. In: 42nd International Symposium on Mathematical Foundations of Computer Science (Aalborg 2017). Leibniz International Proceedings in Informatics, vol. 83, #\u00a030. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"414_CR10","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Gu\u015bpiel, G., Gutowski, G., Krawczyk, T., Liotta, G.: The partial visibility representation extension problem. In: 24th International Symposium on Graph Drawing and Network Visualization (Athens 2016). Lecture Notes in Computer Science, vol. 9801, pp. 266\u2013279. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-50106-2_21"},{"key":"414_CR11","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Lipp, F., Park, J., Wolff, A.: Obstructing visibilities with one obstacle. In: 24th International Symposium on Graph Drawing and Network Visualization (Athens 2016). Lecture Notes in Computer Science, vol. 9801, pp. 295\u2013308. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-50106-2_23"},{"issue":"1","key":"414_CR12","doi-asserted-by":"publisher","first-page":"#\u00a0R79","DOI":"10.37236\/803","volume":"15","author":"AM Dean","year":"2008","unstructured":"Dean, A.M., Ellis-Monaghan, J.A., Hamilton, S., Pangborn, G.: Unit rectangle visibility graphs. Electron. J. Comb. 15(1), #\u00a0R79 (2008)","journal-title":"Electron. J. Comb."},{"issue":"1","key":"414_CR13","doi-asserted-by":"publisher","first-page":"45","DOI":"10.7155\/jgaa.00136","volume":"11","author":"AM Dean","year":"2007","unstructured":"Dean, A.M., Evans, W., Gethner, E., Laison, J.D., Safari, M.A., Trotter, W.T.: Bar $$k$$-visibility graphs. J. Gr. Algorithms Appl. 11(1), 45\u201359 (2007)","journal-title":"J. Gr. Algorithms Appl."},{"issue":"1","key":"414_CR14","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0166-218X(96)00029-7","volume":"75","author":"AM Dean","year":"1997","unstructured":"Dean, A.M., Hutchinson, J.P.: Rectangle-visibility representations of bipartite graphs. Discrete Appl. Math. 75(1), 9\u201325 (1997)","journal-title":"Discrete Appl. Math."},{"key":"414_CR15","doi-asserted-by":"crossref","unstructured":"Di Giacomo, E., Didimo, W., Evans, W.S., Liotta, G., Meijer, H., Montecchiani, F., Wismath, S.K.: Ortho-polygon visibility representations of embedded graphs. In: 24th International Symposium on Graph Drawing and Network Visualization (Athens 2016). Lecture Notes in Computer Science, vol. 9801, pp. 280\u2013294. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-50106-2_22"},{"issue":"16","key":"414_CR16","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1016\/j.ipl.2010.05.023","volume":"110","author":"W Didimo","year":"2010","unstructured":"Didimo, W., Eades, P., Liotta, G.: A characterization of complete bipartite RAC graphs. Inform. Process. Lett. 110(16), 687\u2013691 (2010)","journal-title":"Inform. Process. Lett."},{"issue":"39","key":"414_CR17","doi-asserted-by":"publisher","first-page":"5156","DOI":"10.1016\/j.tcs.2011.05.025","volume":"412","author":"W Didimo","year":"2011","unstructured":"Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156\u20135166 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"414_CR18","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0012-365X(83)90128-0","volume":"46","author":"P Duchet","year":"1983","unstructured":"Duchet, P., Hamidoune, Y., Las Vergnas, M., Meyniel, H.: Representing a planar graph by vertical lines joining different levels. Discrete Math. 46(3), 319\u2013321 (1983)","journal-title":"Discrete Math."},{"key":"414_CR19","doi-asserted-by":"crossref","unstructured":"Eades, P., Hong, S.-H., Poon, Sh.-H.: On rectilinear drawing of graphs. In: 17th International Symposium on Graph Drawing (Chicago 2009). Lecture Notes in Computer Science, vol. 5849, pp. 232\u2013243. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-11805-0_23"},{"key":"414_CR20","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.tcs.2016.06.045","volume":"645","author":"WS Evans","year":"2016","unstructured":"Evans, W.S., Liotta, G., Montecchiani, F.: Simultaneous visibility representations of plane $$st$$-graphs using L-shapes. Theor. Comput. Sci. 645, 100\u2013111 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"414_CR21","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Houle, M.E., Whitesides, S.: New results on a visibility representation of graphs in $$3$$D. In: Symposium on Graph Drawing (Passau 1995). Lecture Notes in Computer Science, vol. 1027, pp. 234\u2013241. Springer, Berlin (1996)","DOI":"10.1007\/BFb0021807"},{"key":"414_CR22","doi-asserted-by":"crossref","unstructured":"Felsner, S.: Rectangle and square representations of planar graphs. In: Thirty Essays on Geometric Graph Theory, pp. 213\u2013248. Springer, New York (2013)","DOI":"10.1007\/978-1-4614-0110-0_12"},{"key":"414_CR23","doi-asserted-by":"crossref","unstructured":"Formann, M., Hagerup, T., Haralambides, J., Kaufmann, M., Leighton, F.T., Simvonis, A., Welzl, E., Woeginger, G.J.: Drawing graphs in the plane with high resolution. In: 31st Annual Symposium on Foundations of Computer Science (St. Louis 1990), vol. 1, pp. 86\u201395. IEEE Computer Society, Los Alamitos (1990)","DOI":"10.1109\/FSCS.1990.89527"},{"key":"414_CR24","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Series of Books in the Mathematical Sciences. W.H. Freeman, San Francisco (1979)"},{"issue":"2","key":"414_CR25","doi-asserted-by":"publisher","first-page":"269","DOI":"10.7155\/jgaa.00393","volume":"20","author":"E Gaub","year":"2016","unstructured":"Gaub, E., Rose, M., Wenger, P.S.: The unit bar visibility number of a graph. J. Gr. Algorithms Appl. 20(2), 269\u2013297 (2016)","journal-title":"J. Gr. Algorithms Appl."},{"key":"414_CR26","unstructured":"Hoffmann, M., T\u00f3th, Cs.D.: Two-planar graphs are quasiplanar (2017). arXiv:1705.05569"},{"key":"414_CR27","unstructured":"Hoffmann, M., T\u00f3th, Cs.D.: Two-planar graphs are quasiplanar. In: 42nd International Symposium on Mathematical Foundations of Computer Science (Aalborg 2017). Leibniz International Proceedings in Informatics, vol. 83, #\u00a047. Leibniz-Zent. Inform., Wadern (2017)"},{"key":"414_CR28","doi-asserted-by":"crossref","unstructured":"Ma\u0148uch, J., Patterson, M., Poon, Sh.-H., Thachuk, Ch.: Complexity of finding non-planar rectilinear drawings of graphs. In: 18th International Symposium on Graph Drawing (Konstanz 2010). Lecture Notes in Computer Science, vol. 6502, pp. 305\u2013316. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-18469-7_28"},{"key":"414_CR29","doi-asserted-by":"crossref","unstructured":"Nilsson, N.J.: A mobile automaton: an application of artificial intelligence techniques. In: 1st International Joint Conference on Artificial Intelligence (Washington 1969), pp. 509\u2013520 (1969)","DOI":"10.21236\/ADA459660"},{"key":"414_CR30","doi-asserted-by":"crossref","unstructured":"Schaefer, Th.J.: The complexity of satisfiability problems. In: 10th Annual ACM Symposium on Theory of Computing (San Diego 1978), pp. 216\u2013226. ACM, New York (1978)","DOI":"10.1145\/800133.804350"},{"key":"414_CR31","doi-asserted-by":"crossref","unstructured":"Streinu, I., Whitesides, S.: Rectangle visibility graphs: characterization, construction, and compaction. In: 20th Annual Symposium on Theoretical Aspects of Computer Science (Berlin 2003). Lecture Notes in Computer Science, vol. 2607, pp. 26\u201337. Springer, Berlin (2003)","DOI":"10.1007\/3-540-36494-3_4"},{"issue":"4","key":"414_CR32","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1(4), 321\u2013341 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"414_CR33","doi-asserted-by":"crossref","unstructured":"Wismath, S.K.: Characterizing bar line-of-sight graphs. In: 1st Annual ACM SIGACT\/SIGGRAPH Symposium on Computational Geometry (Baltimore 1985), pp. 147\u2013152. ACM, New York (1985)","DOI":"10.1145\/323233.323253"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00414-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00414-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00414-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T21:27:28Z","timestamp":1729114048000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00414-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,22]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["414"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00414-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,3,22]]},"assertion":[{"value":"29 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}