2000 character limit reached
Point visibility graph recognition is NP-hard
Published 10 Jun 2014 in cs.CG, cs.CC, and cs.DM | (1406.2428v2)
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.
Paper Prompts
Sign up for free to create and run prompts on this paper using GPT-5.
Top Community Prompts
Collections
Sign up for free to add this paper to one or more collections.
