Joanna Ellis-Monaghan (St. Michael's College)

Problems from the Edge-Graph Theoretical Approaches to Computer Chip Design

Abstract for the Combinatorics and Number Theory Seminar 2003 October 13, Monday (Note special day.)

A major component of computer chip design is generating an optimal netlist layout, i.e., determining where to lay wires (connections between functional elements) when manufacturing a chip. Because of its basic structure (nodes with edges between them!), the overall problem of netlist layout contains many sub-questions that lend themselves to graph theoretical modeling and analysis. We will describe the basic principles of netlist layout, and present several open questions inherent in the problem. Possible approaches to these questions include concepts from hypergraphs, graph partitioning, graph drawing, graph and geometric thickness, tree width, grid graphs, bipartite graphs, planar embeddings, and geometric graph theory. Due to the highly competitive nature of the microelectronics industry, there is strong interest in graph theoretical results that may shorten the chip design cycle.