Convex bipartite graph explained

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 → , 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

• W. Lipski Jr.. Franco P. Preparata. Franco P. Preparata. August 1981. Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica. 15. 4. 329–346. 10.1007/BF00264533. 2142/74215. 39361123. free.
• Ten-hwang Lai. Shu-shang Wei. April 1997. Bipartite permutation graphs with application to the minimum buffer size problem. Discrete Applied Mathematics. 74. 1. 33–55. 10.1016/S0166-218X(96)00014-5. 2009-07-20. free.
• Book: Efficient graph representations. Jeremy P. Spinrad. 2003. AMS Bookstore. 978-0-8218-2815-1 . 128. 2009-07-20.
• Book: Graph classes: a survey. Andreas Brandstädt. Andreas Brandstädt. Van Bang Le . Jeremy P. Spinrad . 1999. SIAM. 978-0-89871-432-6 . 94. registration. convex if there is an ordering.. 2009-07-20.