Power/ground networks in VLSI: are general graphs better than trees?

Power/ground nets in VLSI usually cover a large portion of chip area due to a considerable power consumption of the chips. For multi-layer power/ground networks containing either trees or general graphs, it is an important question whether trees or general graphs can be realized with less total routing area while satisfying identical reliability constraints. In this paper we prove that a general graph (containing at least one loop) can always be replaced by a set of trees with the same or less total routing area, when imposing voltage drop and current density constraints on the power/ground nets and modeling these nets by a resistive network. Moreover every tree with several pads can be replaced by a set of trees, each having only one pad, with the same or less total routing area. Among the trees with only one pad, those trees are area-minimal which have an optimal sizing and contain only tree components with homogeneous current densities. All these statements cannot be generalized to the case of considering minimum width constraints in addition to the voltage drop and current density constraints. To prove the main theorems of the paper, we apply constructive methods, which can be used in CAD tools to optimize given power/ground networks.