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.
Formal definition
Let G = (U ∪ V, E) 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, f: 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
- W. Lipski Jr.; Franco P. Preparata (August 1981). "Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems". Acta Informatica 15 (4): 329–346. doi:10.1007/BF00264533.
- 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. doi:10.1016/S0166-218X(96)00014-5. http://citeseer.ist.psu.edu/old/lai94bipartite.html. Retrieved 2009-07-20.
- Jeremy P. Spinrad (2003). Efficient graph representations. AMS Bookstore. p. 128. ISBN 978-0-8218-2815-1. https://books.google.com/books?id=RrtXSKMAmWgC&dq=%22a+bipartite+graph+is+a+convex+graph%22&pg=PA128. Retrieved 2009-07-20.
- Andreas Brandstädt; Van Bang Le; Jeremy P. Spinrad (1999). Graph classes: a survey. SIAM. p. 94. ISBN 978-0-89871-432-6. https://archive.org/details/graphclassessurv0000bran. Retrieved 2009-07-20. "convex if there is an ordering."
 |  |
