Building vertex-edge visibility graph among polygonal obstacles on 2d plane
I'm not sure if this is what you're after, but here's an $O(n + k)$ approach from J. O'Rourke and I. Streinu, Computational Geometry 10 (1998), pp. 105-120:


  $G_{VE}$ may be constructed in $O(n + k)$ time for a polygon with $n$ vertices and $k$ visibility edges, by a slight modification of Hershberger's algorithm that constructs $G_v$ in this time bound [8] from a polygon triangulation. Supplementing with Chazelle's linear-time triangulation algorithm achieves the claimed bound.