Abstract
Multipatterning is an essential decomposition strategy in electronic design automation (EDA) that overcomes lithographic limitations when printing dense circuit layouts. Although heuristic-based backtracking and SAT solvers can address these challenges, they often struggle to simultaneously handle both complex constraints and secondary objectives such as mask balance. In this thesis, we present a comprehensive study of AI-driven approaches for autonomous graph coloring in multipatterning contexts, systematically comparing Graph Neural Networks (GNN), reinforcement learning (RL), and large language models (LLMs) across initial coloring and solution refinement tasks. We cast multipatterning as a variant of constrained graph coloring with the primary objective of minimizing feature violations and secondary objectives including balancing features across masks.
The pipeline integrates three main components: (1) A GNN-based model, trained in an unsupervised manner to generate initial color predictions, which are refined by (2) Algorithmic refinement strategies (a GNN-based heuristic and simulated annealing) or (3) Learning-based refinement (reinforcement learning and large language models) that together enhance solution quality and balance.
Lastly, we propose an agentic pipeline that autonomously orchestrates multiple AI components through structured tool interactions, enabling dynamic strategy selection and adaptation to novel constraints without human intervention.
Experimental evaluations on both proprietary datasets and publicly available open-source layouts demonstrate that our workflow achieves accurate and balanced coloring assignments with high success rates.
School
School of Sciences and Engineering
Department
Computer Science & Engineering Department
Degree Name
MS in Computer Science
Graduation Date
Fall 2-15-2026
Submission Date
1-24-2026
First Advisor
Nourhan Sakr
Committee Member 1
Hossam Sharara
Committee Member 2
Andrew Kahng
Extent
90 p.
Document Type
Master's Thesis
Institutional Review Board (IRB) Approval
Not necessary for this item
Disclosure of AI Use
Thesis editing and/or reviewing; Code/algorithm generation and/or validation; Data/results generation and/or analysis
Recommended Citation
APA Citation
Helaly, A. W.
(2026).Graph Neural Network Applications in Electronic Design Automation [Master's Thesis, the American University in Cairo]. AUC Knowledge Fountain.
https://fount.aucegypt.edu/etds/2665
MLA Citation
Helaly, Abdelrahaman Wael. Graph Neural Network Applications in Electronic Design Automation. 2026. American University in Cairo, Master's Thesis. AUC Knowledge Fountain.
https://fount.aucegypt.edu/etds/2665