New theoretical results on quadratic placement

Current tools for VLSI placement are based either on quadratic placement, or on min-cut heuristics, or on simulated annealing. For the most complex chips with millions of movable objects, algorithms based on quadratic placement seem to yield the best results within reasonable time. In this paper, we prove several new theoretical results on quadratic placement. We point out connections to random walks and electrical networks. Moreover, we argue that quadratic placement has, in contrast to the other approaches, some well-defined stability properties. Finally, we consider the question how to choose the weights of the clique edges representing a multiterminal net optimally.