Cover Image

Combinatorial Properties and Recognition of Unit Square Visibility Graphs

CC BY

Saved in:
Bibliographic Details
Main Authors: Katrin, Casel, Henning, Fernau, Alexander, Grigoriev
Format: Book
Language:English
Published: Springer 2023
Subjects:
USV
USGV
Online Access:https://link.springer.com/article/10.1007/s00454-022-00414-8
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7553
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-7553
record_format dspace
spelling oai:localhost:PNK-75532023-04-05T04:18:14Z Combinatorial Properties and Recognition of Unit Square Visibility Graphs Katrin, Casel Henning, Fernau Alexander, Grigoriev USV USGV CC BY 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. 2023-04-05T04:18:14Z 2023-04-05T04:18:14Z 2023 Book https://link.springer.com/article/10.1007/s00454-022-00414-8 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7553 en application/pdf Springer
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic USV
USGV
spellingShingle USV
USGV
Katrin, Casel
Henning, Fernau
Alexander, Grigoriev
Combinatorial Properties and Recognition of Unit Square Visibility Graphs
description CC BY
format Book
author Katrin, Casel
Henning, Fernau
Alexander, Grigoriev
author_facet Katrin, Casel
Henning, Fernau
Alexander, Grigoriev
author_sort Katrin, Casel
title Combinatorial Properties and Recognition of Unit Square Visibility Graphs
title_short Combinatorial Properties and Recognition of Unit Square Visibility Graphs
title_full Combinatorial Properties and Recognition of Unit Square Visibility Graphs
title_fullStr Combinatorial Properties and Recognition of Unit Square Visibility Graphs
title_full_unstemmed Combinatorial Properties and Recognition of Unit Square Visibility Graphs
title_sort combinatorial properties and recognition of unit square visibility graphs
publisher Springer
publishDate 2023
url https://link.springer.com/article/10.1007/s00454-022-00414-8
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7553
_version_ 1762365501465427968
score 8.8894005

Similar Items