Point Visibility Graph Recognition is NP-Hard

DOI10.1142/S0218195916500011zbMath1338.68268arXiv1406.2428OpenAlexW2964349067MaRDI QIDQ2809312

Bodhayan Roy

Publication date: 27 May 2016

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

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

zbMATH Keywords

NP-hardrecognition problempoint visibility graph

Mathematics Subject Classification ID

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

Related Items (3)

On colouring point visibility graphs ⋮ Recognition and complexity of point visibility graphs ⋮ Clique-width of point configurations

Cites Work

• On the chromatic number of the visibility graph of a set of points in the plane
• Visibility Algorithms in the Plane
• Unnamed Item

This page was built for publication: Point Visibility Graph Recognition is NP-Hard