On coloring rectangular and diagonal grid graphs for multiple patterning lithography

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

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages387-392
Number of pages6
ISBN (Electronic)9781509006021
DOIs
StatePublished - Feb 20 2018
Event23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018 - Jeju, Korea, Republic of
Duration: Jan 22 2018Jan 25 2018

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
Volume2018-January

Other

Other23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018
CountryKorea, Republic of
CityJeju
Period1/22/181/25/18

    Fingerprint

ASJC Scopus subject areas

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

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