Convex bipartite graph

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

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

Литература

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