Visibility graph

Visibility graph --- граф видимости.

The visibility graph $VG(S)$ of a set $S$ of $n$ disjoint line segments in a plane has a vertex for every endpoint of a segment in $S$, two of them being adjacent when the corresponding points see each other, i.e., the segment they define does not cross any segment in $S$.

The contracted visibility graph $CVG(S)$ of a set $S$ of $n$ disjoint line segments has a vertex for every segment in $S$, two of them, $s_{1}$ and $s_{2}$, being adjacent when some endpoint of $s_{1}$ sees some endpoint of $s_{2}$.

Let $S$ be a set of $n$ disjoint horizontal line segments in the plane without two endpoints having equal abscissa. The bar-visibility graph $BVG(S)$ has a vertex for every segment of $S$, and two segments $s$ and $t$ are adjacent, if there is a vertical segment joining $s$ and $t$ and touching no other segment of $S$.