Point visibility graph recognition is NP-hard

DOI10.1142/S0218195916500011MaRDI QIDQ2809312zbMATH OpenOpenAlexFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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.

Recommendations

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

Cites work

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

Cited in

(5)

• Recognizing tough graphs is NP-hard
• Computational complexity aspects of point visibility graphs
• Recognition and complexity of point visibility graphs
• Clique-width of point configurations
• 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)