## Files in this item

FilesDescriptionFormat

application/pdf

8815431.pdf (4MB)
(no description provided)PDF

## Description

 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 Degree: Ph.D. Genre: Dissertation 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 Type: Text Description: 126 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988. URI: http://hdl.handle.net/2142/69592 Other Identifier(s): (UMI)AAI8815431 Date Available in IDEALS: 2014-12-15 Date Deposited: 1988
﻿