The dfs_* functions are the bottleneck of the vast majority of performance problems we get reported about Graphviz. I’m not aware of any remaining low hanging performance improvement opportunities there. Someone will probably have to consult the literature and come up with an algorithmic network simplex improvement.
Nevertheless, I’ve filed this as another perf test case for us to investigate: 10h SVG Render Process (#2702) · Issues · graphviz / graphviz · GitLab