Input sensitive VLSI layouts for graphs of arbitrary degree

A general method to find area-efficient VLSI layouts of graphs of arbitrary degree is presented. For graphs of maximum degree Δ, the layouts obtained are smaller by a factor of Δ2 than those obtained using existing methods.Optimal planar layouts, and near-optimal nonplanar layouts are also derived for planar graphs of arbitrary degree and gauge. The results span the spectrum between outerplanar graphs (gauge 1), and arbitrary planar graphs (gauge O(n)). Optimality is established by developing families of planar graphs of varying gauge and degree, and proving lower bounds on their layout area. These techniques can be combined to exhibit a trade-off between area and the number of contact cuts. The resulting scheme is sensitive to all three parameters that affect the area: the maximum degree, the gauge, and the number of contact cuts.