This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69592
Description
Title
Algorithms for VLSI Layout
Author(s)
Tollis, Ioannis Georgios
Issue Date
1988
Doctoral Committee Chair(s)
Preparata, Franco P.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
