Stretchability of star-like pseudo-visibility graphs

We present advances on the open problem of characterizingvertex-edge visibility graphs (ve-graphs), reducedby results of O'Rourke and Streinu to a stretchabilityquestion for pseudo-polygons. We introducestar-like pseudo-polygons as a special subclass containingall the known instances of non-stretchable pseudopolygons.We give a complete combinatorial characterizationand a linear-time decision procedure forstar-like pseudo-polygon stretchability and star-likeve-graph recognition.To the ...