Visibility graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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.