We also introduce a new type of polygon visibility graph, the vertex-edge visibility graph. More generally we define the vertex-edge visibility graph for pseudo-polygons. We demonstrate that it encodes more combinatorial information about the pseudo-polygon than does the vertex visibility graph.

We study the reconstruction problem for vertex-edge pseudo-visibility graphs. Given a bipartite graph $G$ satisfying certain properties, which can all be checked in polynomial time, we show that we can define a generalized configuration of points and a pseudo-polygon on it, so that its vertex-edge pseudo-visibility graph is $G$. This provides a full characterization of vertex-edge pseudo-visibility graphs and a polynomial time algorithm for the decision problem. It also implies that the decision problem for visibility graphs of pseudo-polygons is in NP (as opposed to the same problem with regular straight-edge visibility, which is only known to be in PSPACE, cf. Everett). <\body>