Regarding Graphviz itself, I wonder why is there no special layout logic for planar graphs? They can be recognized and embedded on the plane in linear time without intersecting edges, so it would be very nice if some of the Graphviz tools actually did that.
A recent set of minimal graph coloring Graphviz visualizations of mine: https://gitlab.com/nsajko/example_optimally_colored_graphs