On coloring rectangular and diagonal grid graphs for multiple patterning lithography

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

doi:10.1109/ASPDAC.2018.8297354

On coloring rectangular and diagonal grid graphs for multiple patterning lithography

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

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Rectangular and diagonal grid graphs are induced subgraphs of a rectangular or diagonal grid respectively. Their k-coloring problem has direct applications in printing contact/via layouts by multi-patterning 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. In this paper, we conduct a complete analysis of the k-coloring problems on rectangular and diagonal grid graphs, and particularly the NP-completeness of 3-coloring on a diagonal grid graph is proved. In practice, we propose an exact 3-coloring algorithm. Experiments are conducted to verify its effectiveness and performance. Extensions and other results are also discussed.

Original language	English (US)
Title of host publication	ASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	387-392
Number of pages	6
ISBN (Electronic)	9781509006021
DOIs	https://doi.org/10.1109/ASPDAC.2018.8297354
State	Published - Feb 20 2018
Event	23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018 - Jeju, Korea, Republic of Duration: Jan 22 2018 → Jan 25 2018

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
Volume	2018-January

Other

Other	23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018
Country/Territory	Korea, Republic of
City	Jeju
Period	1/22/18 → 1/25/18

ASJC Scopus subject areas

Electrical and Electronic Engineering
Computer Science Applications
Computer Graphics and Computer-Aided Design

Online availability

10.1109/ASPDAC.2018.8297354

Library availability

Discover UIUC Full Text

Cite this

Guo, D., Zhang, H., & Wong, M. D. F. (2018). On coloring rectangular and diagonal grid graphs for multiple patterning lithography. In ASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings (pp. 387-392). (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 2018-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASPDAC.2018.8297354

On coloring rectangular and diagonal grid graphs for multiple patterning lithography. / Guo, Daifeng; Zhang, Hongbo; Wong, Martin D.F.
ASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. p. 387-392 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 2018-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Guo, D, Zhang, H & Wong, MDF 2018, On coloring rectangular and diagonal grid graphs for multiple patterning lithography. in ASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings. Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, vol. 2018-January, Institute of Electrical and Electronics Engineers Inc., pp. 387-392, 23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018, Jeju, Korea, Republic of, 1/22/18. https://doi.org/10.1109/ASPDAC.2018.8297354

Guo D, Zhang H, Wong MDF. On coloring rectangular and diagonal grid graphs for multiple patterning lithography. In ASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings. Institute of Electrical and Electronics Engineers Inc. 2018. p. 387-392. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). doi: 10.1109/ASPDAC.2018.8297354

Guo, Daifeng ; Zhang, Hongbo ; Wong, Martin D.F. / On coloring rectangular and diagonal grid graphs for multiple patterning lithography. ASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 387-392 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

@inproceedings{89f8212f589946759deec8e0f8ec71e7,

title = "On coloring rectangular and diagonal grid graphs for multiple patterning lithography",

abstract = "Rectangular and diagonal grid graphs are induced subgraphs of a rectangular or diagonal grid respectively. Their k-coloring problem has direct applications in printing contact/via layouts by multi-patterning 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. In this paper, we conduct a complete analysis of the k-coloring problems on rectangular and diagonal grid graphs, and particularly the NP-completeness of 3-coloring on a diagonal grid graph is proved. In practice, we propose an exact 3-coloring algorithm. Experiments are conducted to verify its effectiveness and performance. Extensions and other results are also discussed.",

author = "Daifeng Guo and Hongbo Zhang and Wong, {Martin D.F.}",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018 ; Conference date: 22-01-2018 Through 25-01-2018",

year = "2018",

month = feb,

day = "20",

doi = "10.1109/ASPDAC.2018.8297354",

language = "English (US)",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "387--392",

booktitle = "ASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings",

address = "United States",

}

TY - GEN

T1 - On coloring rectangular and diagonal grid graphs for multiple patterning lithography

AU - Guo, Daifeng

AU - Zhang, Hongbo

AU - Wong, Martin D.F.

PY - 2018/2/20

Y1 - 2018/2/20

N2 - Rectangular and diagonal grid graphs are induced subgraphs of a rectangular or diagonal grid respectively. Their k-coloring problem has direct applications in printing contact/via layouts by multi-patterning 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. In this paper, we conduct a complete analysis of the k-coloring problems on rectangular and diagonal grid graphs, and particularly the NP-completeness of 3-coloring on a diagonal grid graph is proved. In practice, we propose an exact 3-coloring algorithm. Experiments are conducted to verify its effectiveness and performance. Extensions and other results are also discussed.

AB - Rectangular and diagonal grid graphs are induced subgraphs of a rectangular or diagonal grid respectively. Their k-coloring problem has direct applications in printing contact/via layouts by multi-patterning 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. In this paper, we conduct a complete analysis of the k-coloring problems on rectangular and diagonal grid graphs, and particularly the NP-completeness of 3-coloring on a diagonal grid graph is proved. In practice, we propose an exact 3-coloring algorithm. Experiments are conducted to verify its effectiveness and performance. Extensions and other results are also discussed.

UR - http://www.scopus.com/inward/record.url?scp=85045349090&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045349090&partnerID=8YFLogxK

U2 - 10.1109/ASPDAC.2018.8297354

DO - 10.1109/ASPDAC.2018.8297354

M3 - Conference contribution

AN - SCOPUS:85045349090

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 387

EP - 392

BT - ASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018

Y2 - 22 January 2018 through 25 January 2018

ER -

On coloring rectangular and diagonal grid graphs for multiple patterning lithography

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this