I think the hard part is more defining the different types of visually pleasing layouts that you want to support. What to align to what, what metrics to minimize, etc.

There is no single layout definition that looks good for all applications. What looks good for one type of graph data (flow charts, org charts, ASTs, family trees, etc, etc) may not look good for another.

Once you've reduced a desired type of layout to a set of layout rules, then I don't think implementing it is the bottleneck, and it seems this part could even be automated if wanted (e.g. evolve layout to best meet constraints).