Convex bipartite graph

In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties. A bipartite graph ${\displaystyle (U\cup V,E)}${\displaystyle (U\cup V,E)} is said to be convex over the vertex set ${\displaystyle U}${\displaystyle U} if ${\displaystyle U}${\displaystyle U} can be enumerated such that for all ${\displaystyle v\in V}${\displaystyle v\in V}, the vertices adjacent to ${\displaystyle v}${\displaystyle v} are consecutive in the enumeration. Convexity over ${\displaystyle V}${\displaystyle V} is defined analogously. A bipartite graph ${\displaystyle (U\cup V,E)}${\displaystyle (U\cup V,E)} that is convex over both ${\displaystyle U}${\displaystyle U} and ${\displaystyle V}${\displaystyle V} is said to be biconvex or doubly convex.^{[1] [2] [3] [4]}

For a biconvex graph with labelings ${\displaystyle U={u_{1},\ldots ,u_{m}}}${\displaystyle U={u_{1},\ldots ,u_{m}}} and ${\displaystyle V={v_{1},\ldots ,v_{n}}}${\displaystyle V={v_{1},\ldots ,v_{n}}}, let ${\displaystyle {\overline {u_{i}}}}${\displaystyle {\overline {u_{i}}}} denote the set of neighbors of vertex ${\displaystyle u_{i}}${\displaystyle u_{i}}. A biconvex graph is called forward-convex if there exists a labeling such that ${\displaystyle V}${\displaystyle V} is convex and the labeling has the forward property: for every pair of vertices ${\displaystyle u_{i},u_{j}\in U}${\displaystyle u_{i},u_{j}\in U} with ${\displaystyle i<j}${\displaystyle i<j}, it holds that ${\displaystyle {\overline {u_{i}}}\supseteq {\overline {u_{j}}}}${\displaystyle {\overline {u_{i}}}\supseteq {\overline {u_{j}}}} (where ${\displaystyle \supseteq }${\displaystyle \supseteq } means that ${\displaystyle {\overline {u_{i}}}}${\displaystyle {\overline {u_{i}}}} contains ${\displaystyle {\overline {u_{j}}}}${\displaystyle {\overline {u_{j}}}} as a consecutive segment).^[2]

It has been proven that forward-convex graphs are equivalent to permutation graphs. A biconvex graph is forward-convex (and hence a bipartite permutation graph) if and only if it contains no induced subgraph isomorphic to certain forbidden configurations.^[2]

Every biconvex graph is a 4-polygon graph, that is, its vertices can be represented as chords inside a convex 4-sided polygon such that two vertices are adjacent if and only if their corresponding chords intersect.^[5] Furthermore, every biconvex graph has a biconvex S-ordering (straight ordering), which is a biconvex ordering that generalizes the strong ordering of bipartite permutation graphs and prohibits certain crossing patterns between edges.^[5]

A strongly biconvex graph is a bipartite graph ${\displaystyle H=(X,Y)}${\displaystyle H=(X,Y)} with labelings ${\displaystyle X={x_{q},x_{q+1},\ldots ,x_{f}}}${\displaystyle X={x_{q},x_{q+1},\ldots ,x_{f}}} and ${\displaystyle Y={y_{q'},y_{q'+1},\ldots ,y_{g}}}${\displaystyle Y={y_{q'},y_{q'+1},\ldots ,y_{g}}} such that if ${\displaystyle {x_{i},y_{j}}}${\displaystyle {x_{i},y_{j}}} is an edge, then ${\displaystyle i<j}${\displaystyle i<j}

For any ${\displaystyle r}${\displaystyle r} with ${\displaystyle i<r<j}${\displaystyle i<r<j} and edge ${\displaystyle {x_{i},y_{j}}}${\displaystyle {x_{i},y_{j}}}: if ${\displaystyle x_{r}\in X}${\displaystyle x_{r}\in X} then ${\displaystyle {x_{r},y_{j}}}${\displaystyle {x_{r},y_{j}}} is an edge, and if ${\displaystyle y_{r}\in Y}${\displaystyle y_{r}\in Y} then ${\displaystyle {x_{i},y_{r}}}${\displaystyle {x_{i},y_{r}}} is an edge.^[6] Every strongly biconvex graph is biconvex and weakly chordal.^[6]

Finding a maximum matching in a convex bipartite graph can be done efficiently. Glover showed that a maximum matching can be found using a greedy algorithm that processes vertices in order.^[7] Subsequent improvements by various researchers culminated in a linear-time algorithm.^[7]

For the dynamic version of the problem, where the graph is modified by vertex and edge insertions and deletions, it is impossible to maintain an explicit representation of a maximum matching in sub-linear time per operation, even in the amortized sense, because a single update can change ${\displaystyle \Theta (|V|)}${\displaystyle \Theta (|V|)} edges in the matching.^[7] However, it is possible to efficiently maintain which vertices are matched: there exists a data structure that maintains the set of matched vertices in ${\displaystyle O(\log ^{2}|V|)}${\displaystyle O(\log ^{2}|V|)} amortized time per update operation, answers whether a given vertex is matched in ${\displaystyle O(1)}${\displaystyle O(1)} worst-case time, and can identify the mate of a matched vertex in ${\displaystyle O({\sqrt {|V|}}\log ^{2}|V|)}${\displaystyle O({\sqrt {|V|}}\log ^{2}|V|)} amortized time.^[7]

A biclique is a complete bipartite subgraph. The maximum edge biclique problem asks for a biclique with the maximum number of edges. In general bipartite graphs, this problem is NP-complete,^[8] but for convex bipartite graphs it can be solved in polynomial time. Given a convex bipartite graph ${\displaystyle G=(A\cup B,E)}${\displaystyle G=(A\cup B,E)} with ${\displaystyle |A|=n}${\displaystyle |A|=n}, a maximum edge biclique can be found in ${\displaystyle O(n\log ^{3}n\log \log n)}${\displaystyle O(n\log ^{3}n\log \log n)} time and ${\displaystyle O(n)}${\displaystyle O(n)} space.^[8] For the special cases of biconvex graphs and bipartite permutation graphs, the problem can be solved even more efficiently in ${\displaystyle O(n\alpha (n))}${\displaystyle O(n\alpha (n))} and ${\displaystyle O(n)}${\displaystyle O(n)} time respectively, where ${\displaystyle \alpha (n)}${\displaystyle \alpha (n)} is the inverse Ackermann function.^[8]

The maximum edge biclique problem has applications in analyzing DNA microarray data, where it corresponds to finding biclusters—subsets of genes that exhibit coherent expression patterns across subsets of experimental conditions.^[8]

An induced matching is a set of edges that are pairwise at distance at least 3. Finding a maximum induced matching is NP-hard for general bipartite graphs, but can be solved efficiently for certain subclasses. For strongly biconvex graphs, a maximum induced matching can be computed in linear time using a greedy algorithm.^[6] Indeed, even a maximum-weight induced matching can be computed in linear-time for any convex bipartite graph using dynamic programming.^[9]

The vertex ranking problem asks for a coloring of vertices with the property that every path between two vertices of the same color must contain a vertex of higher color, using the minimum number of colors. While this problem is NP-complete for general bipartite graphs, it can be solved in polynomial time for biconvex graphs in ${\displaystyle O(n^{4}(n+m))}${\displaystyle O(n^{4}(n+m))} time, where ${\displaystyle n}${\displaystyle n} is the number of vertices and ${\displaystyle m}${\displaystyle m} is the number of edges.^[5]

• Convex plane graph

• Graph families
• Bipartite graphs

• Articles with short description
• Short description matches Wikidata
• Use list-defined references from January 2025