Using XFree86 4.1.0, I experienced the problem I described with both the i386 binary RPMs and with binaries compiled from the sources (for all versions of the Graphviz from 1.7.6 through 1.8.8)
Once I upgraded to XFree86 4.2.0, both the binary RPM installation and the binaries built by me from the source packages worked as expected.
In other words, this wasn't really a bug in Graphviz but rather in
the older XFree86 implementations. I thought I'd submit the report to
follow up on bug report 19 and to help other XFree86 users who might
have been experiencing this problem.
Fix: Upgrade to XFree86 4.2.0
Owner: ek
Status: Fixed (8 July 2002)