I assume that the world supplied represents a configuration space for a 2D polygonal robot in a workspace containing polygonal obstacles. The robot does not rotate, so its configuration space is R2. The visibility graph is constructed naively by attempting to connect every vertex in the environment to every other vertex by a straight edge. Intersection tests are performed against every obstacle in the world. This method obviously would not scale well to large, complex worlds, but it works fine for the simple example worlds presented here.
Rather than constructing the entire visibility graph at the start, only the set of vertices is defined initially. The set of vertices consists of the goal, each corner of a C-space obstacle, and each intersection point between the edges of two obstacles. A* search is performed on the graph, with the edges being dynamically generated as vertices are reached. Initially, only the start state is on the open list. It is popped and all vertices within line of sight are connected to the start and inserted onto the open list. The search proceeds in like manner from here. Note that the obstacles are open sets, so obstacle edges are also valid visibility graph edges. In the examples below, no obstacles share edges (which would result in a line segment connecting two seemingly-non-connected sections of freespace).
In the visualizations here, note that the entire visibility graph is not shown. As A* with a monotone heuristic effectively turns a graph into a tree, that tree is what is shown in the movies. The explored edges are shown in gray. A Euclidean distance heuristic is used for A*. The movies are as follows: