Representing a Planar Straight-Line Graph Using Few Obstacles
Matthew P. Johnson, Deniz Sarıöz · Canadian Conference on Computational Geometry · 2014
An obstacle representation of a planar straight-line graph (PSLG) G consists of the choice and placement of a set of opaque polygonal obstacles in such a way that the visibility graph on V (G) induced by the obstacles equals G (i.e., u and v are visible to one another i ( u;v)2 E(G)). We investigate the problem of computing an obstacle representation of a PSLG, using a minimum number of obstacles. We call this minimum size the obstacle number of the drawing, and the problem of computing it ORPG. First, we show that ORPG is NP-hard by reduction from planar vertex cover, resolving a question posed