On Colourability of Polygon Visibility Graphs

DOI10.4230/LIPIcs.FSTTCS.2017.21zbMath1491.68256arXiv1906.01904MaRDI QIDQ5136313

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

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

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

Related Items (2)

Coloring polygon visibility graphs and their generalizations ⋮ On colourability of polygon visibility graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A game of cops and robbers
• An optimal visibility graph algorithm for triangulated simple polygons
• Hiding people in polygons
• Robot motion planning with uncertainty in control and sensing
• The vertex-edge visibility graph of a polygon
• On colouring point visibility graphs
• Computing the maximum clique in the visibility graph of a simple polygon
• On the chromatic number of the visibility graph of a set of points in the plane
• On k-visibility graphs
• Computational complexity of art gallery problems
• Some NP-hard polygon decomposition problems
• Improved bounds for the conflict-free chromatic art gallery problem
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
• Visibility Algorithms in the Plane
• Visibility graphs of point sets in the plane

This page was built for publication: On Colourability of Polygon Visibility Graphs