Content deleted Content added
Formal def adds technicality but no meaning; convert refs to footnotes. Not convinced this format change is an improvement but it clears the cleanup banner. |
Added illustration and description. |
||
Line 1:
{{Use list-defined references|date=January 2025}}
{{CS1 config|mode=cs1}}
[[File:Convex bipartite graphs.svg|thumb|400px|Both graphs are convex bipartite graphs, because at least one side has edges with consecutive vertices on the other side (when properly ordered). The first is also '''biconvex''', because ''both'' sides have this property with the same vertex ordering, while the second is only convex for one side but cannot be made convex for both sides simultaneously (with any vertex ordering), making it '''singly convex'''.]]
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 [[enumeration|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'''.{{r|lp81|lw97|s03|bls99}}
| |||