A couple of tools may prove useful to be integrated with DEPS. Here are some ideas.
Through DEPS plugins
openc++ (http://opencxx.sourceforge.net/), which provides a C++ parser library (still bad support for templates in 2.8, IIRC)
synopsys (http://synopsis.fresco.org/), a multi-language source code introspection tool
sparse (http://kernel.org/git/?p=devel/sparse/sparse.git;a=summary), Linux Torvald's C semantic parser
OpenDX (http://www.opendx.org/), IBM's Visualization Data Explorer
I finally found a couple of tools out there, from which I may borrow ideas some day. I'd be happy to hear about more of them.
cinclude2dot, originally from Darxus (http://www.chaosreigns.com/code/cinclude2dot/), then taken over by F. Flourish (http://www.flourish.org/cinclude2dot/) is a GPL C/C++-only tool, which apparently has support for grouping, but not for transitive reduction. Should I have searched better, and found it a couple of months ago, maybe graph-includes would have never been developped :)
http://www.tarind.com/depgraph.html has a dependency grapher for python, without transitive reduction as well. It does however allow customisation of project classes, somewhat similar to graph-includes.
OptimalAdvisor (http://javacentral.compuware.com/pasta/) is a refactoring tool, which goes far beyond simple dependency analysis, but is non-free/libre/open-source (also they have a functionally-limited free/gratis edition) and seems to support only java.
codeproject.com has some VisualStudio(tm) plugins targetting C++, which I cannot test, but appear to scale badly for large projects (http://www.codeproject.com/csharp/DependencyGraph.asp).