Point visibility graph recognition is NP-hard

DOI10.1142/S0218195916500011zbMATH Open1338.68268arXiv1406.2428OpenAlexW2964349067MaRDI QIDQ2809312FDOQ2809312

Authors: Bodhayan Roy 

Publication date: 27 May 2016

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

Abstract: Given a 3-SAT formula, a graph can be constructed in polynomial time such that the graph is a point visibility graph if and only if the 3-SAT formula is satisfiable. This reduction establishes that the problem of recognition of point visibility graphs is NP-hard.

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

Recommendations

• Recognition and Complexity of Point Visibility Graphs
• Recognition and complexity of point visibility graphs
• Computational complexity aspects of point visibility graphs

zbMATH Keywords

NP-hardrecognition problempoint 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)

Cites Work

• Computational geometry. Algorithms and applications.
• Visibility Algorithms in the Plane
• On the chromatic number of the visibility graph of a set of points in the plane

Cited In (6)

• Computational complexity aspects of point visibility graphs
• On colouring point visibility graphs
• Clique-width of point configurations
• Recognizing tough graphs is NP-hard
• Recognition and Complexity of Point Visibility Graphs
• Recognition and complexity of point visibility graphs

This page was built for publication: Point visibility graph recognition is NP-hard

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