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: |