Convex bipartite graph

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 ∪ VE), 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 ∪ VE) that is convex over both U and V is said to be biconvex or doubly convex.

Formal definition

Let G = (U ∪ VE) be a bipartite graph, i.e, the vertex set is U ∪ V where U ∩ V = ∅. Let NG(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, fU → { 1, 2, ..., |U| − 1, |U|}, such that for all v ∈ V, for any two vertices x,y ∈ NG(v) ⊆ U there does not exist a z ∉ NG(v) such that f(x) < f(z) < f(y).

See also

  • Convex plane graph

References