In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties.
A bipartite graph
(
U
∪
V
,
E
)
{\displaystyle (U\cup V,E)}
is said to be convex over the vertex set
U
{\displaystyle U}
if
U
{\displaystyle U}
can be enumerated such that for all
v
∈
V
{\displaystyle v\in V}
, the vertices adjacent to
v
{\displaystyle v}
are consecutive in the enumeration. Convexity over
V
{\displaystyle V}
is defined analogously. A bipartite graph
(
U
∪
V
,
E
)
{\displaystyle (U\cup V,E)}
that is convex over both
U
{\displaystyle U}
and
V
{\displaystyle V}
is said to be biconvex or doubly convex.
Properties
For a biconvex graph with labelings
U
=
u
1
,
…
,
u
m
{\displaystyle U={u_{1},\ldots ,u_{m}}}
and
V
=
v
1
,
…
,
v
n
{\displaystyle V={v_{1},\ldots ,v_{n}}}
, let
u
i
¯
{\displaystyle {\overline {u_{i}}}}
denote the set of neighbors of vertex
u
i
{\displaystyle u_{i}}
. A biconvex graph is called forward-convex if there exists a labeling such that
V
{\displaystyle V}
is convex and the labeling has the forward property: for every pair of vertices
u
i
,
u
j
∈
U
{\displaystyle u_{i},u_{j}\in U}
with
i
<
j
{\displaystyle i<j}
, it holds that
u
i
¯
⊇
u
j
¯
{\displaystyle {\overline {u_{i}}}\supseteq {\overline {u_{j}}}}
(where
⊇
{\displaystyle \supseteq }
means that
u
i
¯
{\displaystyle {\overline {u_{i}}}}
contains
u
j
¯
{\displaystyle {\overline {u_{j}}}}
as a consecutive segment).
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.
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. 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.
Strongly biconvex graphs
A strongly biconvex graph is a bipartite graph
H
=
(
X
,
Y
)
{\displaystyle H=(X,Y)}
with labelings
X
=
x
q
,
x
q
+
1
,
…
,
x
f
{\displaystyle X={x_{q},x_{q+1},\ldots ,x_{f}}}
and
Y
=
y
q
′
,
y
q
′
+
1
,
…
,
y
g
{\displaystyle Y={y_{q'},y_{q'+1},\ldots ,y_{g}}}
such that if
x
i
,
y
j
{\displaystyle {x_{i},y_{j}}}
is an edge, then
i
<
j
{\displaystyle i<j}
For any
r
{\displaystyle r}
with
i
<
r
<
j
{\displaystyle i<r<j}
and edge
x
i
,
y
j
{\displaystyle {x_{i},y_{j}}}
: if
x
r
∈
X
{\displaystyle x_{r}\in X}
then
x
r
,
y
j
{\displaystyle {x_{r},y_{j}}}
is an edge, and if
y
r
∈
Y
{\displaystyle y_{r}\in Y}
then
x
i
,
y
r
{\displaystyle {x_{i},y_{r}}}
is an edge.
Every strongly biconvex graph is biconvex and weakly chordal.
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. Subsequent improvements by various researchers culminated in a linear-time algorithm.
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
Θ
(
|
V
|
)
{\displaystyle \Theta (|V|)}
edges in the matching. However, it is possible to efficiently maintain which vertices are matched: there exists a data structure that maintains the set of matched vertices in
O
(
log
2
|
V
|
)
{\displaystyle O(\log ^{2}|V|)}
amortized time per update operation, answers whether a given vertex is matched in
O
(
1
)
{\displaystyle O(1)}
worst-case time, and can identify the mate of a matched vertex in
O
(
|
V
|
log
2
|
V
|
)
{\displaystyle O({\sqrt {|V|}}\log ^{2}|V|)}
amortized time.
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, but for convex bipartite graphs it can be solved in polynomial time. Given a convex bipartite graph
G
=
(
A
∪
B
,
E
)
{\displaystyle G=(A\cup B,E)}
with
|
A
|
=
n
{\displaystyle |A|=n}
, a maximum edge biclique can be found in
O
(
n
log
3
n
log
log
n
)
{\displaystyle O(n\log ^{3}n\log \log n)}
time and
O
(
n
)
{\displaystyle O(n)}
space. For the special cases of biconvex graphs and bipartite permutation graphs, the problem can be solved even more efficiently in
O
(
n
α
(
n
)
)
{\displaystyle O(n\alpha (n))}
and
O
(
n
)
{\displaystyle O(n)}
time respectively, where
α
(
n
)
{\displaystyle \alpha (n)}
is the inverse Ackermann function.
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.
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.
Indeed, even a maximum-weight induced matching can be computed in linear-time for any convex bipartite graph using dynamic programming.
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
O
(
n
4
(
n
+
m
)
)
{\displaystyle O(n^{4}(n+m))}
time, where
n
{\displaystyle n}
is the number of vertices and
m
{\displaystyle m}
is the number of edges.
See also
Convex plane graph
References