mathematics
and
computer
science

LANS

LANS Publications

"A Fast Multigrid Algorithm for Energy Minimization under Planar Density Constraints"

D. Ron, I. Safro, and A. Brandt

SIAM Multiscale Modeling and Simulations, vol. 8, no. 5, , pp. 1599-1620. Also Preprint ANL/MCS-P1560-1108

Preprint Version: [pdf]

The two-dimensional layout optimization problem reinforced by the ecient space utilization demand has a wide spectrum of practical applications. Formulating the problem as a nonlinear minimization problem under planar equality and/or inequality density constraints, we present a linear time multigrid algorithm for solving correction to this problem. The method is demonstrated on various graph drawing (visualization) instances.