There is a chain of dependencies that you need to check. It starts with libgd, then the GD module, then GD::Graph.
So you may need to recompile libgd ( with the latest version), then rebuild GD, then rebuild GD::Graph to get gif support. From the GD readme:
libgd can now be built with support for one or more of the PNG, GIF,
+XPM or JPEG formats. If one or more of these formats are not support
+ed by libgd, then the corresponding GD::Image methods will be unavail
+able.
.......
+
As of libgd 2.0.33, GIF support is always compiled in, so (for the
+time being!) this is a safe fallback.