Linear time algorithms on regular graphs For each constant $k$, the number of $k$-regular graphs is of the order of $n^{\Omega(n)}$. Therefore, we need $O(n\log n)$ bits to represent k-regular graphs unambiguously. 

Let $k=3$ for simplicity. There are several algorithms 
that run in time $O(n)$ on $3$-regular graphs with at most $n$ vertices.
For instance, determining if a graph is bipartite. 

How is that possible, if only to read the input we need to read $O(n\log n)$ bits?
We usually analyze algorithms on the RAM machine model, in which each operation on a machine word has unit cost. A machine word consists of $O(\log n)$ bits, where $n$ is the bit-size of the input, or some other equivalent property. Thus representing a $k$-regular graph takes only $O(n)$ machine words, so there is no contradiction.