ABSTRACT
Ten years (1970-1980) of design automation for layout synthesis produced a small research community with a firm basis in graph theory and a growing awareness of computational complexity. Stephen Cook’s famous theorem was not yet published and complexity issues were tackled by bounding techniques, smart speedups, and of course heuristics. Planar mapping as used in the early design flows started a whole new area in graph theory, the so-called visibility graphs, but without further applications in layout synthesis. Layout synthesis starts with a netlist, that is, an incidence structure or hypergraph with modules as nodes and nets as hyperedges. The intuition behind mincut placement is that if fewer wires cross the first cut lines, there will be fewer long connections in the final layout. Layout synthesis provides masks for chip fabrication, or more precisely, it provides data structures from which masks are derived.
