Convex bipartite graph

In the mathematical field of graph theory, a convex bipartite graph is a special kind of bipartite graph. A bipartite graph $(U,V,E)$ is said to be convex over the vertex set $U$ if $U$ can be ordered such that for all $v\in 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.

See also

• Convex plane graph

References

• W. Lipski Jr. (1981). "Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems". Acta Informatica. 15 (4): 329–346. doi:10.1007/BF00264533. Retrieved 2009-07-20. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help); Unknown parameter |month= ignored (help)
• Ten-hwang Lai (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. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help); Unknown parameter |month= ignored (help)
• Jeremy P. Spinrad (2003). Efficient graph representations. AMS Bookstore. p. 128. ISBN 9780821828151. Retrieved 2009-07-20.
• Andreas Brandstädt (1999). Graph classes: a survey. SIAM. p. 94. ISBN 9780898714326. Retrieved 2009-07-20. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)