Partialk-trees: Algorithms and applications

Partial k-trees are a recursively defined class of graphs that allow efficient algorithms for a variety of combinatorial optimization problems. An $O(n\sp2$) algorithm for the Bisection Width problem on partial k-trees is presented. The $O(n\sp2$) Bi-section width algorithm forms the basis for a polynomial time grid embedding for partial k-trees. The embedding is provably good, in the sense that the resulting layout is no more than O(A log$\sp4$ N) where A is the optimal layout for any N node, degree 4, partial k-tree. A Theory of Structure Preserving Expansions is presented and characterized. The machinery for successively deriving partial k-trees, as a hierarchy of graphs of bounded complexity has been developed. The graphs at each level are derived by expanding the parent graphs at the previous level. The expansion process is Structure Preserving, in the sense that each expanded graph is a partial $k\sp\prime$-tree for some $k\sp\prime$. The expansion of planar partial k trees is considered in detail and bounds on $k\sp\prime$ are developed for the important case of expanding tree subgraphs of the parent graphs. A linear time algorithm for the Steiner tree problem on partial k-trees is presented. This is also the largest class of graphs for which a polynomial time Steiner tree algorithm is currently known. The framework of structure preserving expansions and the linear time algorithm for the Steiner tree problem have been applied to the physical design of VLSI circuits. An optimal algorithm for hierarchical floorplanning and Global Routing has been developed. The hierarchical floorplanning algorithm developed in this thesis, allows expansion of modules to any fixed k modules at a lower level, without placing any restrictions on the geometry of the placement