Publication details
On Colourability of Polygon Visibility Graphs
Authors | |
---|---|
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 | |
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: |