Convex bipartite graph
Introduction 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'' → {1, …, |''U''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 ****