On Colourability of Polygon Visibility Graphs

Onur Çağirici, Petr Hliněný, Bodhayan Roy

We study the problem of colouring visibility graphs of polygons. In particular, for visibility graphs of simple polygons, we provide a polynomial algorithm for 4-colouring, and prove that the 5-colourability question is already NP-complete for them. For visibility graphs of polygons with holes, we prove that the 4-colourability question is NP-complete.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment