Kraftwerk (Force-Directed Placement)

The idea

Where GORDIAN spreads cells with constraints, Kraftwerk spreads them with forces. Compute the current cell-density field over the die; treat overfilled areas as positive charge; solve a Poisson equation to get the potential this charge creates; its negative gradient is a spreading force field. Add each cell's local spreading force to the spring system as a constant pull and re-solve the quadratic; cells migrate from dense areas toward empty ones. Recompute density, forces, solve again; iterate until the density is acceptably even. Fixed obstacles simply appear as permanent charge, so macros and blockages repel cells with no special code.

The formulation is uniform: one mechanism handles spreading, obstacle avoidance, and even timing weights (stronger springs on critical nets). Kraftwerk2 later gave the scheme a firmer footing (bound-to-bound net model making the quadratic model exact for half-perimeter wirelength, and a better-behaved two-force iteration with provable-flavored convergence behavior).

Trade-offs

Against GORDIAN-style constraint refinement, force iteration is simpler, faster per step, and more flexible; its risks are oscillation and drift (forces are recomputed from stale density, and naive schedules orbit instead of settling), which the second-generation formulation largely tamed.

Where you meet it today

Its density-as-potential idea, solved by fast Poisson methods, is the direct ancestor of ePlace's electrostatics, today's dominant formulation; and 'force-directed' remains the umbrella name for this entire way of thinking about spreading.