  The representation complexity of a bipartite graph $G=(P,Q)$ is the minimum
size $\sum_{i=1}^s (|A_i|+|B_i|)$ over all possible ways to write $G$ as a (not
necessarily disjoint) union of complete bipartite subgraphs $G=\cup_{i=1}^s
A_i\times B_i$ where $A_i\subset P, B_i\subset Q$ for $i=1,\dots, s$. In this
paper we prove that if $G$ is \emph{semi-algebraic}, i.e. when $P$ is a set of
$m$ points in $\mathbb{R}^{d_1}$, $Q$ is a set of $n$ points in
$\mathbb{R}^{d_2}$ and the edges are defined by some semi-algebraic relations,
the representation complexity of $G$ is $O(
m^{\frac{d_1d_2-d_2}{d_1d_2-1}+\varepsilon}
n^{\frac{d_1d_2-d_1}{d_1d_2-1}+\varepsilon}+m^{1+\varepsilon}+n^{1+\varepsilon})$
for arbitrarily small positive $\varepsilon$. This generalizes results by
Apfelbaum-Sharir and Solomon-Sharir. As a consequence, when $G$ is
$K_{u,u}$-free for some positive integer $u$, its number of edges is $O(u
m^{\frac{d_1d_2-d_2}{d_1d_2-1}+\varepsilon}
n^{\frac{d_1d_2-d_1}{d_1d_2-1}+\varepsilon}+ u m^{1+\varepsilon}+u
n^{1+\varepsilon})$. This bound is stronger than that of Fox, Pach, Sheffer,
Suk and Zahl when the first term dominates and $u$ grows with $m,n$. Another
consequence is that we can find a large complete bipartite subgraph in a
semi-algebraic graph when the number of edges is large. Similar results hold
for semi-algebraic hypergraphs.
