Detailed Information on Publication Record
2018
On Colourability of Polygon Visibility Graphs
CAGIRICI, Onur, Petr HLINĚNÝ and Bodhayan ROYBasic information
Original name
On Colourability of Polygon Visibility Graphs
Authors
CAGIRICI, Onur (792 Turkey, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution) and Bodhayan ROY (356 India, belonging to the institution)
Edition
LIPIcs 93. Dagstuhl, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), p. "21:1"-"21:14", 14 pp. 2018
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Germany
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
electronic version available online
RIV identification code
RIV/00216224:14330/18:00100735
Organization unit
Faculty of Informatics
ISBN
978-3-95977-055-2
ISSN
Keywords in English
polygon visibility graph; graph coloring; NP-completeness
Tags
Tags
International impact, Reviewed
Změněno: 14/6/2022 12:06, RNDr. Pavel Šmerk, Ph.D.
Abstract
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.
Links
| GA17-00837S, research and development project |
| ||
| MUNI/A/0854/2017, interní kód MU |
| ||
| MUNI/A/0897/2016, interní kód MU |
| ||
| MUNI/A/0992/2016, interní kód MU |
|