TY - JOUR
T1 - On Coloring Rectangular and Diagonal Grid Graphs for Multipatterning and DSA Lithography
AU - Guo, Daifeng
AU - Zhang, Hongbo
AU - Wong, Martin D. F.
N1 - Funding Information:
Manuscript received June 14, 2018; revised October 19, 2018 and February 1, 2019; accepted March 17, 2019. Date of publication May 7, 2019; date of current version May 22, 2020. This work was supported in part by the National Science Foundation under Grant CCF-1421563 and Grant CCF-171883. Preliminary version of this paper titled as “On Coloring Rectangular and Diagonal Grid Graphs for Multiple Patterning Lithography” is presented at 2018 IEEE/ACM Asia and South Pacific Design Automation Conference, Jeju Island, South Korea, January 2018 [1]. This paper was recommended by Associate Editor C. Chu. (Corresponding author: Daifeng Guo.) D. Guo and M. D. F. Wong are with the Department of Electrical and Computer Engineering, University of Illinois at Urbana– Champaign, Champaign, IL 61801 USA (e-mail: [email protected]; [email protected]).
Publisher Copyright:
© 1982-2012 IEEE.
PY - 2020/6
Y1 - 2020/6
N2 - 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.
AB - 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.
KW - Design for manufacturing (DFM)
KW - directed self-assembly (DSA)
KW - graph algorithm
KW - grid graph
KW - k-coloring
KW - multiple patterning lithography (MPL)
UR - http://www.scopus.com/inward/record.url?scp=85086272012&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2019.2915326
DO - 10.1109/TCAD.2019.2915326
M3 - Journal article
AN - SCOPUS:85086272012
SN - 0278-0070
VL - 39
SP - 1205
EP - 1216
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 6
ER -