Thông tin tài liệu
Nhan đề : |
Combinatorial Properties and Recognition of Unit Square Visibility Graphs |
Tác giả : |
Katrin, Casel Henning, Fernau Alexander, Grigoriev |
Năm xuất bản : |
2023 |
Nhà xuất bản : |
Springer |
Tóm tắt : |
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. |
Mô tả: |
CC BY |
URI: |
https://link.springer.com/article/10.1007/s00454-022-00414-8 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7553 |
Bộ sưu tập |
OER - Khoa học Tự nhiên |
XEM MÔ TẢ
19
XEM TOÀN VĂN
34
Danh sách tệp tin đính kèm: