Back to search

University of Victoria (Canada)

Embedding graphs into rectilinear grids

Abstract

dc:description.abstract

An 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

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gao, Yude. Embedding graphs into rectilinear grids. Master of Science M.Sc. thesis, 1987. https://hdl.handle.net/1828/17856