Convex Bipartite Graph

In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties.
A bipartite graph, (''U'' ∪ ''V'', ''E''), 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 (''U'' ∪ ''V'', ''E'') that is convex over both ''U'' and ''V'' is said to be biconvex or doubly convex.

Formal definition

Let ''G'' = (''U'' ∪ ''V'', ''E'') be a bipartite graph, i.e., the vertex set is ''U'' ∪ ''V'' where ''U'' ∩ ''V'' = ∅.
Let ''N''_''G''(''v'') 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'' ∈ ''N''_''G''(''v'') ⊆ ''U'' there does not exist a ''z'' ∉ ''N''_''G''(''v'') such that ''f''(''x'') < ''f''(''z'') < ''f''(''y'').

See also

* Convex plane graph

References

*
*
*
*

Graph families
Bipartite graphs

{{graph-stub