Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1799092,
author = {Agaoglu, Deniz and Cagirici, Onur},
address = {Cham},
booktitle = {Extended Abstracts EuroComb 2021},
doi = {http://dx.doi.org/10.1007/978-3-030-83823-2_61},
editor = {Nešetřil, Jaroslav and Perarnau, Guillem and Rué, Juanjo and Serra, Oriol},
keywords = {unit disk graphs; visibility graphs; 3-coloring problem; NP-hardness},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Cham},
isbn = {978-3-030-83822-5},
pages = {390-396},
publisher = {Springer International Publishing},
title = {Unit Disk Visibility Graphs},
year = {2021}
}
TY - JOUR
ID - 1799092
AU - Agaoglu, Deniz - Cagirici, Onur
PY - 2021
TI - Unit Disk Visibility Graphs
PB - Springer International Publishing
CY - Cham
SN - 9783030838225
KW - unit disk graphs
KW - visibility graphs
KW - 3-coloring problem
KW - NP-hardness
N2 - 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.
ER -
AGAOGLU, Deniz and Onur CAGIRICI. Unit Disk Visibility Graphs. In Nešetřil, Jaroslav and Perarnau, Guillem and Rué, Juanjo and Serra, Oriol. \textit{Extended Abstracts EuroComb 2021}. Cham: Springer International Publishing. p.~390-396. ISBN~978-3-030-83822-5. doi:10.1007/978-3-030-83823-2\_{}61. 2021.
|
