The graphviz package stores some libraries in /usr/lib/graphviz, but they don't show up in searches. Creating the file "/etc/env.d/50graphviz" containing LDPATH=/usr/lib/graphviz fixed it. It should be in the ebuild, though.
This looks like a duplicate of bug 118092. Do you have any examples of where this is needed?
*** This bug has been marked as a duplicate of 118092 ***