On colouring point visibility graphs
From MaRDI portal
Publication:2201772
DOI10.1016/j.dam.2019.01.018zbMath1448.05072arXiv1610.00952MaRDI QIDQ2201772
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
NP-completeness; graph colouring; chromatic number; visibility graph; point set; point visibility graph
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