Files in this item
|(no description provided)|
|Title:||Algorithms for VLSI Layout|
|Author(s):||Tollis, Ioannis Georgios|
|Doctoral Committee Chair(s):||Preparata, Franco P.|
|Department / Program:||Computer Science|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Subject(s):||Engineering, Electronics and Electrical
|Abstract:||This thesis considers several problems arising during VLSI layout and presents new techniques for solving them efficiently.
We propose a linear-time algorithm for generating a planar layout of a planar graph with n vertices. The vertices are represented by horizontal line segments and the edges by vertical line segments. This layout occupies area at most n by 2n $-$ 4 and contains no bends. Next, we investigate two variants of this representation and we present characterizations of the classes of graphs that admit such representations. Furthermore, we present linear time algorithms for testing the existence of and constructing visibility representations. We also consider planar embeddings, where vertices are mapped to grid points and edges are mapped to pairwise nonintersecting grid paths.
The problem of wiring a given layout in a uniform grid is a fundamental problem in VLSI layout. We present a systematic approach to wiring layouts in the octo-square grid. This approach is based on the concept of two-colorable maps. The algorithms for obtaining the wiring of a layout run in time linear with respect to the area occupied by the layout. Moreover, this approach is extended to wiring layouts in other uniform grids. We also present a new technique for wiring layouts in the square grid. This technique gives rise to two new algorithms for wiring layouts in the square grid and the tri-hexagonal grid. Finally, we briefly discuss the problem of stretching layouts in order to obtain wirability.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988.
|Date Available in IDEALS:||2014-12-15|