New graph bipartizations for double-exposure, bright field alternating phase-shift mask layout

We describe new graph bipartization algorithms for layout modification and phase assignment of bright-field alternating phase-shifting masks (AltPSM). The problem of layout modification for phase-assignability reduces to the problem of making a certain layout-derived graph bipartite (i.e., 2-colorable). Previous work by Berman et al. (2000) solves bipartization optimally for the dark field alternating PSM regime. Only one degree of freedom is allowed (and relevant) for such a bipartization: edge deletion, which corresponds to increasing the spacing between features in order to remove phase conflict. Unfortunately, dark-field PSM is used only for contact layers, due to limitations of negative photoresists. Poly and metal layers are actually created using positive photoresists and bright-field masks. In this paper, we define a new graph bipartization formulation that pertains to the more technologically relevant bright-field regime. The previous work by Berman et al. does not apply to this regime. This formulation allows two degrees of freedom for layout perturbation: (i) increasing the spacing between features, and (ii) increasing the width of critical features. Each of these corresponds to node deletion in a new layout-derived graph that we define, called the feature graph. Graph bipartization by node deletion asks for a minimum weight node set A such that deletion of A makes the graph bipartite. Unlike bipartization by edge deletion, this problem is NP-hard. We investigate several practical heuristics for the node deletion bipartization of planar graphs, including one that has 9/4 approximation ratio. Computational experience with industrial VLSI layout benchmarks shows promising results