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)}$ is said to be convex over the vertex set ${\displaystyle U}$ if ${\displaystyle U}$ can be enumerated such that for all ${\displaystyle v\in V}$, the vertices adjacent to ${\displaystyle v}$ are consecutive in the enumeration. Convexity over ${\displaystyle V}$ is defined analogously. A bipartite graph ${\displaystyle (U\cup V,E)}$ that is convex over both ${\displaystyle U}$ and ${\displaystyle V}$ is said to be biconvex or doubly convex.^[1][2][3][4]

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.

Properties

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

Strongly biconvex graphs

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

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

Algorithms

Maximum matching

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|)}$ 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|)}$ amortized time per update operation, answers whether a given vertex is matched in ${\displaystyle O(1)}$ worst-case time, and can identify the mate of a matched vertex in ${\displaystyle O({\sqrt {|V|}}\log ^{2}|V|)}$ amortized time.^[7]

Maximum edge biclique

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)}$ with ${\displaystyle |A|=n}$, a maximum edge biclique can be found in ${\displaystyle O(n\log ^{3}n\log \log n)}$ time and ${\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))}$ and ${\displaystyle O(n)}$ time respectively, where ${\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]

Maximum induced matching

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]

Vertex ranking

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))}$ time, where ${\displaystyle n}$ is the number of vertices and ${\displaystyle m}$ is the number of edges.^[5]

See also

• Convex plane graph