Recently I was trying to run doxygen on a new machine and got this error :
sh: dot: command not found
After some googling I realized I was missing graphviz dot, so a simple yum install graphviz fixed it right up.
Refhat, centos, rhel
yum install graphviz
Debian, Ubuntu, Mint etc
apt-get install graphviz
This will install graphviz dot and get rid of your dot command not found error. If you have any further issues post in the comments and hopefully we can resolve it.