On Colourability of Polygon Visibility Graphs

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CAGIRICI Onur HLINĚNÝ Petr ROY Bodhayan

Year of publication 2018
Type Article in Proceedings
Conference 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.21
Field Informatics
Keywords polygon visibility graph; graph coloring; NP-completeness
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.