Abstract
dc:description.abstractAn embedding of one graph into another is a mapping of the guest nodes into the host nodes plus a compatible mapping of the guest edges into paths in the host. Graph embeddings model many significant problems in computer science. This thesis surveys techniques for embedding graphs into rectangular grids. These techniques are particularly relevant to VLSI circuit layout. Two important factors in VLSI layout are chip area and maximum wire length. These factors are modelled in a graph embedding by the expansion and dilation of the embedding. We mainly discuss the problem of minimizing the area of the grid into which the graph (i.e., circuit) is embedded. Our survey includes results that have been obtained by various researchers for both single layer and multi-layer embeddings. The survey covers trees, outerplanar graphs , planar graphs and thickness k graphs. We also describe some new results for outerplanar graphs and thickness k graphs. For complete binary trees, the so called H embedding requires only linear area. In this embedding there are only O(√n) leaves on the boundary of the grid. If we require that all leaves be embedded on the boundary, then it has been shown that Ω(n log n ) area is necessary. For trees in general, two different divide-and-conquer methods are described. Either of them gives us O(n) embedding area for trees with bounded degree.
Degree
thesis:*- Level thesis:degree_level
- Master of Science M.Sc.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 1987
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Gao, Yude
Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1828/17856