In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a convex bipartite graph is a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
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
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
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