Этот модуль вызывает системные консольные утилиты (dot и neato) напрямую. Т.е. проблема, возможно, в них.
Если .dot-файл с русским языком сделать, то команда dot его обработает корректно?
Вообще, можно ещё тупо влезть в /usr/share/php/Image/GraphViz.php (в твоём дистрибутиве расположение может отличаться), найти строку ~329:
code php
$command = $this->binPath . (($command == 'dot')
? $this->dotCommand
: $this->neatoCommand);
Это формирование команды. Следом идёт:
code php
@`$command`;
исполнение команды.
Вот между ними вставить:
code php
посмотреть, что будет напечатано и посмотреть сохранённые временные файлы, что в них. Если с кодировкой всё хорошо, то виновата команда dot. Если плохо — то PHP
… чтобы понять рекурсию, нужно сперва понять рекурсию …