Back to Search Start Over

Combinatorial Properties and Recognition of Unit Square Visibility Graphs

Authors :
Casel, Katrin
Fernau, Henning
Grigoriev, Alexander
Schmid, Markus L.
Whitesides, Sue
Larsen, Kim G.
Bodlaender, Hans L.
Raskin, Jean-Francois
QE Operations research
RS: GSBE ETBC
Data Analytics and Digitalisation
RS: GSBE Theme Data-Driven Decision-Making
RS: FSE DACS Mathematics Centre Maastricht
Source :
Maastricht University, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 83, 30:1-30:15, Discrete & Computational Geometry, 69, 937-980. Springer Verlag
Publication Year :
2023
Publisher :
Springer Science and Business Media LLC, 2023.

Abstract

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 $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard, which settles an open question.

Details

ISSN :
14320444 and 01795376
Volume :
69
Database :
OpenAIRE
Journal :
Discrete & Computational Geometry
Accession number :
edsair.doi.dedup.....82bb39ee60e39da3f3ce27dd35b1bd2b