Visibility graph

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

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

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

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