On Colourability of Polygon Visibility Graphs

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

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: