On colouring point visibility graphs

DOI10.1016/j.dam.2019.01.018zbMath1448.05072arXiv1610.00952MaRDI QIDQ2201772

Bodhayan Roy, Ajit A. Diwan

Publication date: 17 September 2020

Published in: Discrete Applied Mathematics, Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

NP-completeness; graph colouring; chromatic number; visibility graph; point set; point visibility graph

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

On Colourability of Polygon Visibility Graphs, Computational complexity aspects of point visibility graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Recognition and complexity of point visibility graphs
• On the connectivity of visibility graphs
• The power of geometric duality
• Some results on point visibility graphs
• On the chromatic number of the visibility graph of a set of points in the plane
• Point Visibility Graph Recognition is NP-Hard
• Constructing Arrangements of Lines and Hyperplanes with Applications
• On planar point sets with the pentagon property
• Recognition and Complexity of Point Visibility Graphs
• Unsolved problems in visibility graphs of points, segments, and polygons
• Visibility Algorithms in the Plane
• Sur le coloriage des graphs
• Visibility graphs of point sets in the plane