Graph-based legalization for PCB placement

Abstract With the rapid advancement of consumer electronics, printed circuit board (PCB) placement is becoming increasingly complex because of irregular layout regions and routing constraints. To address these challenges, this paper proposes an efficient legalization algorithm that eliminates footprint overlap and improves profitability. We first construct a constraint graph to represent the positional relationships among footprints while preserving the geometric characteristics of the placement. Then, by optimizing appropriate objective costs, we implement adaptive packing strategies that enhance placement quality while maintaining the initial placement features. Finally, an iterative adjustment process ensures that the final placement meets all legalization constraints. Based on real-world industrial layout samples, experimental results demonstrate that our algorithm efficiently minimizes wire length and ratsnets intersections while ensuring 100% legality.