 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2024) (Learn how and when to remove this message) |
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
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. hdl:2142/74215. S2CID 39361123.
- 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. Retrieved 2009-07-20.
- Jeremy P. Spinrad (2003). Efficient graph representations. AMS Bookstore. p. 128. ISBN 978-0-8218-2815-1. 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. Retrieved 2009-07-20.
convex if there is an ordering.
 | This graph theory-related article is a stub. You can help Misplaced Pages by expanding it. |