$O(m+n)$ really necessary for graph algorithms? It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.).

For nearly all such algorithms, vertices of degree zero have no effect on the underlying graph problem. So a solution to the graph problem can usually treat all these unsupported vertices jointly, and does not need to process them individually. For example, in depth-first-search, it suffices to list the dfs-tree for the supported vertices, along with an auxiliary record that all other vertices are unsupported.

If the graph is presented with any kind of intelligent data structure, it should be possible to process in time $O(m)$, and to generate a data structure that encodes the solution in time $O(m)$. This applies even in the case that $n \gg m$.

My question is, what is the reason for the notation $O(m+n)$? Are there really algorithms which require this running time $\Omega(n)$ in the regime $n \gg m$? Is this basically for pedagogical purposes only?
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.