Unit Disk Visibility Graphs

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

AGAOGLU Deniz CAGIRICI Onur

Rok publikování 2021
Druh Článek ve sborníku
Konference Extended Abstracts EuroComb 2021
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1007/978-3-030-83823-2_61
Klíčová slova unit disk graphs; visibility graphs; 3-coloring problem; NP-hardness
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.