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

Daifeng Guo, Hongbo Zhang, Martin D.F. Wong

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number8708289
Pages (from-to)1205-1216
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number6
StatePublished - Jun 2020
Externally publishedYes


  • Design for manufacturing (DFM)
  • directed self-assembly (DSA)
  • graph algorithm
  • grid graph
  • k-coloring
  • multiple patterning lithography (MPL)

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'On Coloring Rectangular and Diagonal Grid Graphs for Multipatterning and DSA Lithography'. Together they form a unique fingerprint.

Cite this