Files in this item



application/pdf8815431.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Algorithms for VLSI Layout
Author(s):Tollis, Ioannis Georgios
Doctoral Committee Chair(s):Preparata, Franco P.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Computer Science
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.
Issue Date:1988
Description:126 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988.
Other Identifier(s):(UMI)AAI8815431
Date Available in IDEALS:2014-12-15
Date Deposited:1988

This item appears in the following Collection(s)

Item Statistics