On colourability of polygon visibility graphs

DOI10.4230/LIPICS.FSTTCS.2017.21MaRDI QIDQ5136313zbMATH OpenFDO

Authors Onur Çağırıcı, Petr Hliněný, Bodhayan Roy

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1906.01904

zbMATH Keywords

graph coloringNP-completenesspolygon visibility graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

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

Recommendations

• Coloring polygon visibility graphs and their generalizations
• scientific article; zbMATH DE number 4085050
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS

Cites work

• A game of cops and robbers
• An optimal visibility graph algorithm for triangulated simple polygons
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
• Computational complexity of art gallery problems
• Computing the maximum clique in the visibility graph of a simple polygon
• Hiding people in polygons
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved bounds for the conflict-free chromatic art gallery problem
• On k-visibility graphs
• On the chromatic number of the visibility graph of a set of points in the plane
• Robot motion planning with uncertainty in control and sensing
• Some NP-hard polygon decomposition problems
• The vertex-edge visibility graph of a polygon
• Tight bounds for conflict-free chromatic guarding of orthogonal art galleries
• Visibility Algorithms in the Plane
• Visibility graphs of point sets in the plane

Cited in

(7)

• Polyominos and perfect graphs
• Helly-type theorems for appropriate colorings of visibility sets
• Four colouring the vertices of the triangulation of a polygon containing a hole
• A P-Completeness Result for Visibility Graphs of Simple Polygons
• A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems
• Coloring polygon visibility graphs and their generalizations
• On colourability of polygon visibility graphs

This page was built for publication: On colourability of polygon visibility graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136313)