Obstructing Visibilities with One Obstacle

Obstacle representations of graphs have been investigated quite intensely over the last few years. We focus on graphs that can be represented by a single obstacle. Given a (topologically open) non-self-intersecting polygon C and a finite set P of points in general position in the complement of C, the visibility graph \(G_C(P)\) has a vertex for each point in P and an edge pq for any two points p and q in P that can see each other, that is, \(\overline{pq} \cap C=\emptyset \). We draw \(G_C(P)\) straight-line and call this a visibility drawing. Given a graph G, we want to compute an obstacle representation of G, that is, an obstacle C and a set of points P such that \(G=G_C(P)\). The complexity of this problem is open, even when the points are exactly the vertices of a simple polygon and the obstacle is the complement of the polygon—the simple-polygon visibility graph problem.