On colouring point visibility graphs

DOI10.1007/978-3-319-53007-9_14zbMATH Open1448.05072arXiv1610.00952OpenAlexW2918091014MaRDI QIDQ2201772FDOQ2201772

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)

Abstract: In this paper we show that it can be decided in polynomial time whether or not the visibility graph of a given point set is 4-colourable, and such a 4-colouring, if it exists, can also be constructed in polynomial time. We show that the problem of deciding whether the visibility graph of a point set is 5-colourable, is NP-complete. We give an example of a point visibility graph that has chromatic number 6 while its clique number is only 4.

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

Recommendations

• On colouring point visibility graphs
• On colourability of polygon visibility graphs
• On the chromatic number of the visibility graph of a set of points in the plane
• Visibility graphs of point sets in the plane
• Computational complexity aspects of point visibility graphs

zbMATH Keywords

chromatic numberNP-completenessgraph colouringpoint setvisibility graphpoint visibility graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Sur le coloriage des graphs
• Computational geometry. Algorithms and applications.
• The power of geometric duality
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Visibility Algorithms in the Plane
• 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
• Recognition and complexity of point visibility graphs
• Recognition and Complexity of Point Visibility Graphs
• Unsolved problems in visibility graphs of points, segments, and polygons
• Visibility graphs of point sets in the plane
• On the connectivity of visibility graphs
• On planar point sets with the pentagon property

Cited In (8)

• Helly-type theorems for appropriate colorings of visibility sets
• Computational complexity aspects of point visibility graphs
• Some results on point visibility graphs
• On the chromatic number of the visibility graph of a set of points in the plane
• On colourability of polygon visibility graphs
• On Colourability of Polygon Visibility Graphs
• Visibility graphs of point sets in the plane
• Coloring polygon visibility graphs and their generalizations

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

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