Convex bipartite graph

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. 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]

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] Indeed, even a maximum-weight induced matching can be computed in linear-time for any convex bipartite graph using dynamic programming.^[9]

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

References

1. W. Lipski Jr.; Franco P. Preparata (August 1981). "Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems". Acta Informatica. 15 (4): 329–346. doi:10.1007/BF00264533. hdl:2142/74215. S2CID 39361123.
2. Ten-hwang Lai; Shu-shang Wei (April 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.
3. Jeremy P. Spinrad (2003). Efficient graph representations. AMS Bookstore. p. 128. ISBN 978-0-8218-2815-1. Retrieved 2009-07-20.
4. Andreas Brandstädt; Van Bang Le; Jeremy P. Spinrad (1999). Graph classes: a survey. SIAM. p. 94. ISBN 978-0-89871-432-6. Retrieved 2009-07-20. convex if there is an ordering.
5. Nesrine Abbas; Lorna K. Stewart (2000). "Biconvex graphs: ordering and algorithms". Discrete Applied Mathematics. 103 (1–3): 1–19. doi:10.1016/S0166-218X(99)00217-6.
6. Sara Saeedi Madani; Dariush Kiani (2021). "Induced matchings in strongly biconvex graphs and some algebraic applications". Mathematische Nachrichten. 294 (7): 1371–1389. arXiv:1905.02640v1. doi:10.1002/mana.201900472.
7. Gerth Stølting Brodal; Loukas Georgiadis; Kristoffer Arnsfelt Hansen; Irit Katriel (2007). Dynamic Matchings in Convex Bipartite Graphs. International Workshop on Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science. Vol. 4769. Springer. pp. 406–417. doi:10.1007/978-3-540-74456-6_37.
8. Doron Nussbaum; Shuye Pu; Jörg-Rüdiger Sack; Takeaki Uno; Hamid Zarrabi-Zadeh (2010). Finding Maximum Edge Bicliques in Convex Bipartite Graphs. International Computing and Combinatorics Conference. Lecture Notes in Computer Science. Vol. 6196. Springer. pp. 140–149. doi:10.1007/978-3-642-14031-0_17.
9. Boris Klemz; Günter Rote (1 April 2022). "Linear-Time Algorithms for Maximum-Weight Induced Matchings and Minimum Chain Covers in Convex Bipartite Graphs". Algorithmica. 84 (4): 1064–1080. arXiv:1711.04496. doi:10.1007/s00453-021-00904-w.