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.{{r|lp81|lw97|s03|bls99}}

References

{{reflist|refs=

{{cite journal|author=W. Lipski Jr.|author2=Franco P. Preparata|author2-link=Franco P. Preparata|date=August 1981|title=Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems|journal=Acta Informatica|volume=15|issue=4|pages=329–346|doi=10.1007/BF00264533|hdl=2142/74215|s2cid=39361123|hdl-access=free}}

{{cite journal|author=Ten-hwang Lai|author2=Shu-shang Wei|date=April 1997|title=Bipartite permutation graphs with application to the minimum buffer size problem|journal=Discrete Applied Mathematics|volume=74|issue=1|pages=33–55|doi=10.1016/S0166-218X(96)00014-5|url=http://citeseer.ist.psu.edu/old/lai94bipartite.html|accessdate=2009-07-20|doi-access=free}}

{{cite book|title=Efficient graph representations|author=Jeremy P. Spinrad|year=2003|publisher=AMS Bookstore|isbn= 978-0-8218-2815-1 |page=128|url=https://books.google.com/books?id=RrtXSKMAmWgC&dq=%22a+bipartite+graph+is+a+convex+graph%22&pg=PA128|accessdate=2009-07-20}}

{{cite book|title=Graph classes: a survey|author=Andreas Brandstädt|author-link=Andreas Brandstädt|author2=Van Bang Le |author3=Jeremy P. Spinrad |year=1999|publisher=SIAM|isbn=978-0-89871-432-6 |page=[https://archive.org/details/graphclassessurv0000bran/page/94 94]|url=https://archive.org/details/graphclassessurv0000bran|url-access=registration|quote=convex if there is an ordering.|accessdate=2009-07-20}}

}}

Category:Graph families

Category:Bipartite graphs

Convex bipartite graph

See also

References