Circuit Verification via Hypergraph Realization

One of the most challenging and time consuming tasks in VLSI design automation is Layout Versus Schematic (LVS). The problem is to test the consistency between the actual circuit, represented by the layout, and the nominal circuit upon which the design was based. From mathematical point of view the core problem is the Hypergraph Isomorphism Problem (HIP)

Unfortunately, it is known as NP-hard, so (as for most of CAD problems) it is extremely important to investigate the frequently encountered particular cases. It is well-known fact that particular case of HIP – Graph Isomorphism Problem – becomes easy solvable when input graphs are planar or have bounded parameters. Following this association, the series of investigations were done for estimation of complexity of the HIP in case of planar hypergraphs. Despite of this problem was proven as NP-hard even for very restricted input parameters, some polynomial-time algorithms were invented for cases when most of hyperedges (they correspond to particular VLSI subcircuits) have the bounded capacity. Fortunately, the classifi ed polynomially-solvable for planarity test hypergraphs are in the same time (being planar) easy checkable on isomorphism. This provides the real breakthrough in effi ciency of LVS tools used in Celebrity (Silvaco suite for VLSI Design Automation) for wide class of integrated circuits.