Convex bipartite graph: Difference between revisions

Revision as of 01:38, 18 December 2009

Latest revision as of 10:47, 26 June 2025

(31 intermediate revisions by 18 users not shown)

Line 1:

{{Short description|Two-sided graph with consecutive neighbors}}

In the [[mathematical]] field of [[graph theory]], a '''convex bipartite graph''' is a special kind of [[bipartite graph]]. A bipartite graph <math>(U,V,E)</math> is said to be convex over the vertex set <math>U</math> if <math>U</math> can be [[total order|ordered]] such that for all <math>v\in V</math> the vertices adjacent to <math>v</math> are consecutive. Convexity over <math>V</math> is defined analogously. A bipartite graph <math>(U,V,E)</math> that is convex over both <math>U</math> and <math>V</math> is said to be '''biconvex''' or '''doubly convex'''.

{{Use list-defined references|date=January 2025}}

{{CS1 config|mode=cs1}}

[[File:Convex bipartite graphs.svg|thumb|400px|Both graphs are convex bipartite graphs, because at least one side has edges with consecutive vertices on the other side (when properly ordered). The first is also '''biconvex''', because ''both'' sides have this property with the same vertex ordering, while the second is only convex for one side but cannot be made convex for both sides simultaneously (with any vertex ordering), making it '''singly convex'''.]]

In the [[mathematical]] field of [[graph theory]], a '''convex bipartite graph''' is a [[bipartite graph]] with specific properties.

InA thebipartite [[mathematical]] field of [[graph theory]], a (''U'convex bipartite graph'&nbsp;∪&nbsp;'' is a special kind of [[bipartite graph]]. A bipartite graph <math>(U,V'',&nbsp;''E'')</math>, is said to be convex over the vertex set <math>''U</math>'' if <math>''U</math>'' can be [[total orderenumeration|orderedenumerated]] such that for all <math>''v\in ''&nbsp;∈&nbsp;''V</math>'' the vertices adjacent to <math>''v</math>'' are consecutive. Convexity over <math>''V</math>'' is defined analogously. A bipartite graph <math>(''U,''&nbsp;∪&nbsp;''V'',&nbsp;''E'')</math> that is convex over both <math>''U</math>'' and <math>''V</math>'' is said to be '''biconvex''' or '''doubly convex'''.{{r|lp81|lw97|s03|bls99}}

==See also==

Line 5 ⟶ 10:

==References==

{{reflist|refs=

*{{cite journal|author=W. Lipski Jr.|coauthors=[[Franco P. Preparata]]|year=1981|month=August|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|url=http://www.springerlink.com/content/u18656lrg6424n3u/|accessdate=2009-07-20}}

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

*{{cite book|title=Efficient graph representations|author=Jeremy P. Spinrad|year=2003|publisher=[[American Mathematical Society|AMS]] Bookstore|isbn= 9780821828151 |page=128|url=http://books.google.com/books?id=RrtXSKMAmWgC&pg=PA128&lpg=PA128&dq=%22a+bipartite+graph+is+a+convex+graph%22&source=bl&ots=yGk0yc2zOX&sig=qFU4rfIPtgJox13M_KWStZBGUCc&hl=de&ei=j1pkSphHhaadA8mirfgP&sa=X&oi=book_result&ct=result&resnum=1|accessdate=2009-07-20}}

*{{cite book|title=Graph classes: a survey||author=Andreas Brandstädt|coauthors=Van Bang Le; Jeremy P. Spinrad|year=1999|publisher=[[Society for Industrial and Applied Mathematics|SIAM]]|isbn=9780898714326 |page=94|url=http://books.google.com/books?id=es9ZbB6qHRYC&pg=PA94&lpg=PA94&dq=%22convex+if+there+is+an+ordering%22&source=bl&ots=WfjGhRyLbE&sig=hz-vHvyUON8bzjF7CvhYvlbqg5k&hl=de&ei=kVtkSvHBBtSksAah5tXpDw&sa=X&oi=book_result&ct=result&resnum=1|accessdate=2009-07-20}}

*<ref name=lp81>{{cite journal|author=W. Lipski Jr.|coauthorsauthor2=[[Franco P. Preparata]]|yearauthor2-link=1981Franco P. Preparata|monthdate=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|urlhdl=http://www.springerlink.com/content/u18656lrg6424n3u2142/74215|accessdates2cid=200939361123|hdl-07-20access=free}}</ref>

{{math-stub}}

*<ref name=lw97>{{cite journal|author=Ten-hwang Lai|coauthorsauthor2=Shu-shang Wei|yeardate=April 1997|month=April|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}}</ref>

*<ref name=s03>{{cite book|title=Efficient graph representations|author=Jeremy P. Spinrad|year=2003|publisher=[[American Mathematical Society|AMS]] Bookstore|isbn= 9780821828151978-0-8218-2815-1 |page=128|url=httphttps://books.google.com/books?id=RrtXSKMAmWgC&pg=PA128&lpg=PA128&dq=%22a+bipartite+graph+is+a+convex+graph%22&sourcepg=bl&ots=yGk0yc2zOX&sig=qFU4rfIPtgJox13M_KWStZBGUCc&hl=de&ei=j1pkSphHhaadA8mirfgP&sa=X&oi=book_result&ct=result&resnum=1PA128|accessdate=2009-07-20}}</ref>

<ref name=bls99>{{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=[[Society for Industrial and Applied Mathematics|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}}</ref>

}}

[[Category:Graph families]]

[[Category:Bipartite graphs]]

{{mathgraph-stub}}