A simple way to find the feasible region of a system with simple constraints
This can be formulated as a linear programming (LP) problem. Arbitrarily state that $A$ is at coordinate 0, then for your example graph we get equations

$$ A = 0$$
$$ B-A \ge 1 $$
$$ C-A \ge 1 $$
$$ 1 \ge C-B \ge 0 $$
$$ \dots $$
$$ F - E \ge 3 $$
$$ F - A = 15 $$

In particular, with $V$ nodes and $E$ edges, we have $V-1$ variables and at most $2E$ linear constraints. Linear programs can be solved in polynomial time (via e.g. the ellipsoid method), but it's not necessarily linear -- more like quadratic or cubic. However! You have a very sparse system: each constraint has only two nonzero entries. This means it will likely perform very well in practice. If you use a free (and usually very well optimized) library, like Gurobi or GLPK, they can use the Simplex method and pretty efficiently use the sparsity.

I realize this might not be completely satisfactory, but: LP solvers are pretty intelligent, and I'm not convinced there's a whole lot more structure to your problem that you could take advantage of that they won't. They will probably do something sort of like your take-min-first strategy, and then "fix" appropriately, and efficiently.

Finally, quick note: You didn't really specify what your goal is, but the solver will want some function to minimize. I would have suggested just saying "minimize $F$", but in your example graph $F$ is actually fixed. So a reasonable objective function might be "minimize $B+C+D+E+F$" or something. Depends on your application. But this should get you basically linear runtime on nearly all cases.