Unit Disk Visibility Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00125020" target="_blank" >RIV/00216224:14330/21:00125020 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-030-83823-2_61" target="_blank" >http://dx.doi.org/10.1007/978-3-030-83823-2_61</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-83823-2_61" target="_blank" >10.1007/978-3-030-83823-2_61</a>
Alternative languages
Result language
angličtina
Original language name
Unit Disk Visibility Graphs
Original language description
We study unit disk visibility graphs, where the visibility relation between a pair of geometric entities is defined by not only obstacles, but also the distance between them. This particular graph class models real world scenarios more accurately compared to the conventional visibility graphs. We first define and classify the unit disk visibility graphs, and then show that the 3-coloring problem is NP-complete when unit disk visibility model is used for a set of line segments (which applies to a set of points) and for a polygon with holes.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA20-04567S" target="_blank" >GA20-04567S: Structure of tractable instances of hard algorithmic problems on graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Extended Abstracts EuroComb 2021
ISBN
9783030838225
ISSN
2297-0215
e-ISSN
—
Number of pages
7
Pages from-to
390-396
Publisher name
Springer International Publishing
Place of publication
Cham
Event location
Cham
Event date
Jan 1, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—