Unit Disk Visibility Graphs

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

AGAOGLU Deniz CAGIRICI Onur

Year of publication 2021
Type Article in Proceedings
Conference Extended Abstracts EuroComb 2021
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-030-83823-2_61
Keywords unit disk graphs; visibility graphs; 3-coloring problem; NP-hardness
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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info