On Coloring Rectangular and Diagonal Grid Graphs for Multipatterning and DSA Lithography.

Rectangular grid graph (RGG) and diagonal grid graph (DGG) are induced subgraphs of a rectangular or diagonal grid, respectively. Their $k$ -coloring problem has direct applications in printing contact/via layouts by multipatterning lithography (MPL). However, the problem in general is computationally difficult for $k>2$ , while it remains an open question on grid graphs due to their regularity and sparsity. On the other hand, directed self-assembly (DSA) technique can work with MPL to optimize the graph by grouping neighboring vertices such that $k$ can be reduced, but the problem of deploying the grouping for coloring is even more intractable. In this paper, we study both of the $k$ -coloring problems, with and without DSA grouping, on RGG and DGG. Without grouping, a complete $k$ -coloring analysis is conducted and particularly the NP-completeness of 3-coloring on a diagonal grid is proved. When considering grouping, we present a 3-coloring solution and prove the NP-completeness to solve the problem of $k=2$. [ABSTRACT FROM AUTHOR]