On colouring point visibility graphs

DOI10.1016/j.dam.2019.01.018zbMath1448.05072arXiv1610.00952OpenAlexW2918091014MaRDI 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-completenessgraph colouringchromatic numbervisibility graphpoint setpoint visibility graph

Mathematics Subject Classification ID

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)

Related Items (3)

On colourability of polygon visibility graphs ⋮ Computational complexity aspects of point visibility graphs ⋮ On Colourability of Polygon 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

This page was built for publication: On colouring point visibility graphs