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.^[1][2][3][4]

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.

See also

• Convex plane graph