2026-07-21T03:11:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8077 2024-03-06T10:40:52Z ddc:004 open_access

Combinatorial Properties and Recognition of Unit Square Visibility Graphs Casel, Katrin Fernau, Henning Grigoriev, Alexander Schmid, Markus L. Whitesides, Sue Visibility graphs visibility layout NP-completeness exact algorithms Unit square (grid) visibility graphs (USV and USGV, resp.) are described by axis-parallel visibility between unit squares placed (on integer grid coordinates) in the plane. We investigate combinatorial properties of these graph classes and the hardness of variants of the recognition problem, i.e., the problem of representing USGV with fixed visibilities within small area and, for USV, the general recognition problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Katrin Casel and Henning Fernau and Alexander Grigoriev and Markus L. Schmid and Sue Whitesides 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.30 urn:nbn:de:0030-drops-80770 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.30 eng https://creativecommons.org/licenses/by/3.0/legalcode