Ok, this is postponed for now. One of the bugs I was going to report was already reported:
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=778478 The maintainer points out that the default value for HAVE_DOT is NO, so he's reluctant to add the build-dependency. But this is only true in doxygen upstream. The problem is that Debian doxygen changes the default for HAVE_DOT to YES (in debian/patches/dot-config.diff), telling doxygen that it may assume that the "dot" command is installed. But this is inconsistent with having graphviz in the Suggests line for doxygen. So either doxygen does not change the default value for HAVE_DOT, or, if it does, it should have graphviz in the Depends line. I've reported this as Bug#818787. The maintainer (Matthias) will have to decide. The disappoining moral for this is that nobody looks at their build logs... Thanks.