Non-stretchable pseudo-visibility graphs.
Ileana Streinu · 1999
We exhibit a family of graphs which can be realized as pseudo-visibility graphs of pseudo-polygons, but not of straight-line polygons. The construction is based on the characterization of vertex-edge pseudo-visibility graphs of O'Rourke and Streinu[ORS96] and extends recent results on non-stretchable vertex-edge visibility graphs of Streinu [Str99]. We show that there is a pseudo-visibility graphs for which there exists only one of vertex-edge visibility graph compatible with it, which is then shown to be non-stretchable. The construction is then extended to an infinite family. 1 Introduction Characterizing visibility graphs is a problem with a distinguished history (Ghosh[Gho88], Everett[Ev90], Abello and Kumar[AK95]), but so far several attempts to give good sets of conditions have been proved insufficient. A different approach, introduced by O'Rourke and Streinu [ORS96] is to separate the combinatorial aspects of the problem from the questions of stretchability (known to be notori...