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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

8 Citations (Scopus)

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
Title of host publication	2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC)
Publisher	IEEE
Pages	387-392
Number of pages	6
ISBN (Electronic)	9781509006021
ISBN (Print)	9781509006038 (Print on Demand)
DOIs	https://doi.org/10.1109/ASPDAC.2018.8297354
Publication status	Published - Jan 2018
Event	23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018 - Jeju, Korea, Republic of Duration: 22 Jan 2018 → 25 Jan 2018 https://www.aspdac.com/aspdac2018/ (Link to conference website) https://tsys.jp/aspdac/2018/program/program.html (Link to conference programme)

Publication series

Name	Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC)

Conference

Conference	23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018
Country/Territory	Korea, Republic of
City	Jeju
Period	22/01/18 → 25/01/18
Internet address	https://www.aspdac.com/aspdac2018/ (Link to conference website) https://tsys.jp/aspdac/2018/program/program.html (Link to conference programme)

Access to Document

10.1109/ASPDAC.2018.8297354

Cite this

@inproceedings{010ee568d333443d861abcd91ca9adfa,

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 = "Funding information: This work is partially supported by the National Science Foundation under Grant CCF-1421563 and CCF-171883; 23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018 ; Conference date: 22-01-2018 Through 25-01-2018",

year = "2018",

month = jan,

doi = "10.1109/ASPDAC.2018.8297354",

language = "English",

isbn = "9781509006038 (Print on Demand)",

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

publisher = "IEEE",

pages = "387--392",

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

address = "United States",

url = "https://www.aspdac.com/aspdac2018/, https://tsys.jp/aspdac/2018/program/program.html",

}

Guo, D, Zhang, H & Wong, MDF 2018, On coloring rectangular and diagonal grid graphs for multiple patterning lithography. in 2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC)., 8297354, Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC), IEEE, pp. 387-392, 23rd Asia and South Pacific Design Automation Conference, ASP-DAC 2018, Jeju, Korea, Republic of, 22/01/18. 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.
2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC). IEEE, 2018. p. 387-392 8297354 (Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC)).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

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.

N1 - Funding information: This work is partially supported by the National Science Foundation under Grant CCF-1421563 and CCF-171883

PY - 2018/1

Y1 - 2018/1

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 - https://www.scopus.com/record/display.uri?eid=2-s2.0-85045349090&origin=inward

U2 - 10.1109/ASPDAC.2018.8297354

DO - 10.1109/ASPDAC.2018.8297354

M3 - Conference proceeding

SN - 9781509006038 (Print on Demand)

T3 - Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC)

SP - 387

EP - 392

BT - 2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC)

PB - IEEE

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

Conference

Access to Document

Other files and links

Fingerprint

Cite this