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
Volume2018-January
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

Other

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

Fingerprint

Coloring
Lithography
Printing
Experiments

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 (Vol. 2018-January, pp. 387-392). 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. Vol. 2018-January Institute of Electrical and Electronics Engineers Inc., 2018. p. 387-392.

Research output: Chapter in Book/Report/Conference proceedingConference 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. 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. Vol. 2018-January. Institute of Electrical and Electronics Engineers Inc. 2018. p. 387-392 https://doi.org/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. Vol. 2018-January Institute of Electrical and Electronics Engineers Inc., 2018. pp. 387-392
@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}",
year = "2018",
month = "2",
day = "20",
doi = "10.1109/ASPDAC.2018.8297354",
language = "English (US)",
volume = "2018-January",
pages = "387--392",
booktitle = "ASP-DAC 2018 - 23rd Asia and South Pacific Design Automation Conference, Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
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

VL - 2018-January

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.

ER -