Convex bipartite graph


In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties.
A bipartite graph,, is said to be convex over the vertex set U if U can be enumerated such that for all v ∈ V the vertices adjacent to v are consecutive.
Convexity over V is defined analogously. A bipartite graph that is convex over both U and V is said to be biconvex or doubly convex.

Formal definition

Let G = be a bipartite graph, i.e., the vertex set is U ∪ V where U ∩ V = ∅.
Let NG denote the neighborhood of a vertex v ∈ V.
The graph G is convex over U if and only if there exists a bijective mapping, f: U → , such that for all v ∈ V,
for any two vertices x,y ∈ NG ⊆ U there does not exist a z ∉ NG such that f < f < f.