Hi, Alejo Hausner!

We worked on this problem, too, and Gordon Woodhull created a working system for dynamic hierarchical layout. I think he also incorporated an improved node positioning and edge routing algorithm of Ulrik Brandes. The code is still available here, I think: https://www.dynagraph.org

It was great work. We meant well, but were overextended for the resources we had. Gordon is a brilliant programmer.

I have looked at Graphviz before, but wasn't aware of anything there that helped with these constraints Do you happen to have any specofic pointers?

And it may be the case that (5) is actually the most implrtant constraint. Haha.

You could probably satisfy 5 with some kind of (mixed integer) linear optimization or so.

Would you mind elaborating? Thanks ahead of time.

Well, you formulate all your constraints in the language of your favourite constraint based programming solver (eg convex optimisation or mixed integer linear optimisation etc). For simplicity, let's call your candidate solution x (where x is a vector of suitable size) and the constraints are formulated as some function f from your vector to real numbers, so that the problem reduces to "minimize f(x)".

Then it's relatively easy to formulate your (5) as an additional constraint in the same language:

Given a previous solution x_0, find a new solution x_1 to slightly different constraints f_1 by minimizing af_1(x_1) + bdistance(x_1-x0)

You'd need to decide on the weights a and b and on the distance function. (Instead combining distance from old solution and constraints linearly, you could also use other ways to combine them. Eg you could also say:

Keep f_1(x_1) <= epsilon and minimize distance(x_1-x_0). Or you could do minimize the sum of squares:

af_1(x_1)^2 + bdistance(x_1-x0)^2

Specifics depends on what works well for your problem, and what your solver can handle.

See https://developers.google.com/optimization for a free library of solvers.