If you have installed the prerequisites properly, I am afraid I've no idea what your problem is.
I did a fresh install of 12.04
Installed the prerequisites thus
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 12.04 LTS
Checked I'd got libguile.h
$ sudo apt-get install build-essential
$ sudo apt-get install guile-1.8-dev
$ sudo apt-get install libsdl1.2-dev
$ sudo apt-get install libsdl-image1.2-dev
Yes, I have, so get the source and build it...
$ find /usr/include -name "*guile*"
and it builds without error. What are you doing differently?
$ wget http://download.savannah.gnu.org/releases/libgraph/libgraph-1.0.2.tar.gz
$ tar xf libgraph-1.0.2.tar.gz
$ cd libgraph-1.0.2/