  We study a parameter of bipartite graphs called readability, introduced by
Chikhi et al. (Discrete Applied Mathematics, 2016) and motivated by
applications of overlap graphs in bioinformatics. The behavior of the parameter
is poorly understood. The complexity of computing it is open and it is not
known whether the decision version of the problem is in NP. The only known
upper bound on the readability of a bipartite graph (following from a work of
Braga and Meidanis, LATIN 2002) is exponential in the maximum degree of the
graph.
  Graphs that arise in bioinformatic applications have low readability. In this
paper, we focus on graph families with readability $o(n)$, where $n$ is the
number of vertices. We show that the readability of $n$-vertex bipartite chain
graphs is between $\Omega(\log n)$ and $O(\sqrt{n})$. We give an efficiently
testable characterization of bipartite graphs of readability at most $2$ and
completely determine the readability of grids, showing in particular that their
readability never exceeds $3$. As a consequence, we obtain a polynomial time
algorithm to determine the readability of induced subgraphs of grids. One of
the highlights of our techniques is the appearance of Euler's totient function
in the analysis of the readability of bipartite chain graphs. We also develop a
new technique for proving lower bounds on readability, which is applicable to
dense graphs with a large number of distinct degrees.
