Item Infomation


Title: 
Combinatorial Properties and Recognition of Unit Square Visibility Graphs
Authors: 
Katrin, Casel
Henning, Fernau
Alexander, Grigoriev
Issue Date: 
2023
Publisher: 
Springer
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 NP -hard.
Description: 
CC BY
URI: 
https://link.springer.com/article/10.1007/s00454-022-00414-8
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7553
Appears in Collections
OER - Khoa học Tự nhiên
ABSTRACTS VIEWS

19

FULLTEXT VIEWS

34

Files in This Item: