On Colourability of Polygon Visibility Graphs

CAGIRICI, Onur, Petr HLINĚNÝ a Bodhayan ROY. On Colourability of Polygon Visibility Graphs. Online. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). LIPIcs 93. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, s. "21:1"-"21:14", 14 s. ISBN 978-3-95977-055-2. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.21.

Základní údaje

Originální název

On Colourability of Polygon Visibility Graphs

Autoři

CAGIRICI, Onur (792 Turecko, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí) a Bodhayan ROY (356 Indie, domácí)

Vydání

LIPIcs 93. Dagstuhl, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), od s. "21:1"-"21:14", 14 s. 2018

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/18:00100735

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-055-2

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.21

Klíčová slova anglicky

polygon visibility graph; graph coloring; NP-completeness

Štítky

core_B, firank_B, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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

---

Návaznosti

GA17-00837S, projekt VaV	Název: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems
MUNI/A/0854/2017, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VII. Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VII., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0897/2016, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VI. Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VI., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0992/2016, interní kód MU	Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU) Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty