Obstructing Visibilities with One ObstacleChaplick, Steven and Lipp, Fabian and Park, Jiwon and Wolff, Alexander (2016) Obstructing Visibilities with One Obstacle. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 295308(Official URL: http://dx.doi.org/10.1007/9783319501062_23). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_23
AbstractObstacle 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) nonselfintersecting polygon C and a finite set P of points in general position in the complement of C, the visibility graph GC(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, pq¯∩C=∅. We draw GC(P) straightline 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=GC(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 simplepolygon visibility graph problem. There are two types of obstacles; outside obstacles lie in the unbounded component of the visibility drawing, whereas inside obstacles lie in the complement of the unbounded component. We show that the class of graphs with an insideobstacle representation is incomparable with the class of graphs that have an outsideobstacle representation. We further show that any graph with at most seven vertices has an outsideobstacle representation, which does not hold for a specific graph with eight vertices. Finally, we show NPhardness of the outsideobstacle graph sandwich problem: given graphs G and H on the same vertex set, is there a graph K such that G⊆K⊆H and K has an outsideobstacle representation. Our proof also shows that the simplepolygon visibility graph sandwich problem, the insideobstacle graph sandwich problem, and the singleobstacle graph sandwich problem are all NPhard.
Actions (login required)
