J 2024

On Colourability of Polygon Visibility Graphs

CAGIRICI, Onur; Petr HLINĚNÝ a Bodhayan ROY

Základní údaje

Originální název

On Colourability of Polygon Visibility Graphs

Autoři

Vydání

EUROPEAN JOURNAL OF COMBINATORICS, ENGLAND, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2024, 0195-6698

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Impakt faktor

Impact factor: 0.900

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/24:00139104

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

EID Scopus

Klíčová slova anglicky

polygon visibility graph; graph coloring; NP-completeness

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 18. 3. 2025 10:01, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

We study the problem of colouring visibility graphs of polygons. In particular, for visibility graphs of simple polygons, we provide a polynomial algorithm for 4-colouring, and prove that the 5-colourability question is already NP-complete for them. For visibility graphs of polygons with holes, we prove that the 4-colourability question is NP-complete.

Návaznosti

GA20-04567S, projekt VaV
Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech
Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs