I have found the answer.
The problem was in installation of graphviz. I have installed graphviz from source code (Source Code | Graphviz) rather than using package manager. For graphviz to correctly display HTML tables, it requires expat-devel.
The lesson is: install things using package manager.
Interestingly, graphviz provided very little information on what was wrong when rendering graphs. There was a very sparse warning about rendering HTML tables, which slipped through my fingers several times.