On the barrier graph of an arrangement of ray sensors

The main result of this paper is a rigidity theorem on the structure of barrier graphs that results from constraints imposed by the geometry of the network. This allows us to show that almost all bipartite graphs are not barrier graphs, despite the fact that various classes of bipartite graphs, including trees, cycles of even length, and Km,n are barrier graphs. Furthermore, vertex cover of a barrier graph corresponds to a set of sensors whose removal allows a clear path from α to β. While all bipartite graphs with small vertex covers are barrier graphs (a fact we prove for sizes less than 4), the rigidity property also implies that graphs with vertex covers bigger than a certain constant are not barrier graphs.