Convex bipartite graph

Convex bipartite graph — выпуклый двудольный граф.

Let [math]\displaystyle{ \,G = (X,Y,E) }[/math] be a bipartite graph. An ordering of [math]\displaystyle{ \,X }[/math] has the adjacency property if for each [math]\displaystyle{ \,y \in Y }[/math] the neighbors of [math]\displaystyle{ \,y }[/math] in [math]\displaystyle{ \,X }[/math] are consecutive in the ordering of [math]\displaystyle{ \,X }[/math]. A bipartite graph [math]\displaystyle{ \,G }[/math] is called convex bipartite if there is an ordering of [math]\displaystyle{ \,X }[/math] or of [math]\displaystyle{ \,Y }[/math] that has the adjacency property. A bipartite graph [math]\displaystyle{ \,G = (X,Y,E) }[/math] is biconvex if there is an ordering of [math]\displaystyle{ \,X }[/math] and [math]\displaystyle{ \,Y }[/math] with the adjacency property. Convex graphs contain the bipartite permutation graphs.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.