$O(m+n)$ really necessary for graph algorithms?
Even when stored very efficiently, vertices with zero degree must be stored in some nonzero space (otherwise, how can we say they even exist)?  That said, they can be stored and searched more efficiently than $O(|V| + |E|)$ using similar ideas to what you describe.

For example, you could just take a standard data structure for storing graphs and store the set of nodes $V' \subseteq V$ which have degree greater than 0.  We don't need to store any information about $V_0$, the set of nodes with degree 0, except for how many there are.

In other words, in a graph with vertices $V$ and edges $E$, if we define

$V' = \{v\in V | v \mbox{ has degree} &gt; 0\}$

$V_0 = \{v\in V | v \mbox{ has degree }  0\}$

We can store the nodes with nonzero degree in $O(|V'| + |E|)$ space, and the nodes with zero degree in $O(\log |V_0|)$ space, giving a total of $O(|V'| + |E| + \log |V_0|)$ space.  

Many algorithms that run in linear time, for example BFS and DFS, will run in time $O(|V'| + |E|)$ because the algorithm can just ignore the vertices with degree zero.  Like you say, if $n &gt;&gt; m$, this is much more efficient than the standard algorithm.

There are many cases where algorithms are parameterized by factors in addition to the size of the input.  Other examples of this include 


Output-sensitive algorithms like range queries for range trees, which run in time $O(\log n + k)$ where $k$ is the size of the query returned.  
Succinct data structures, which store data in space proportional to the entropy of the stored data
Algorithms in the external memory model (section 2 of that in particular--in fact the lecture notes for Erik Demaine's class on Data Structures deal with most of these concepts) depend on the size of a cache and the size of a block transferred from the cache to the processor.
Sparse matrix data structures, and similar structures and algorithms for sparse graphs, which are probably the most similar to what you're asking about.


Most of the references here are fairly general/low level, but there are a great deal of research papers on many of these topics.  In any case, there are sometimes good reasons to use another parameter while analyzing an algorithm's running time, but for general algorithms like DFS, it's assumed that no special data structure or storage methodology is used, leading to $O(|V| + |E|)$ time.