Unit Disk Visibility Graphs

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:	Structure of tractable instances of hard algorithmic problems on graphs Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21 Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.