VL25401 Graph Theory for VLSI Engineers Syllabus:

VL25401 Graph Theory for VLSI Engineers Syllabus – Anna University UG Syllabus Regulation 2025

Course Objective:
This course aims to equip VLSI design engineers with a strong foundation in graph theory concepts and algorithms relevant to various stages of VLSI design, including logic synthesis, physical design and design verification.

Fundamentals of Graph Theory and Graph Representations in VLSI
Introduction to Graphs: Definitions: Vertices, Edges, Directed/Undirected Graphs, Weighted Graphs, Graph Representations- Adjacency Matrix, Adjacency List, Incidence Matrix, Paths, Cycles, Connectivity, Trees, Forests, Graph Isomorphism.
Graph fundamentals: Graph categories- Hypergraph, Graphs with parallel edges, Graphs without parallel edges, Weighted graph, Directed graph- Inter-graph relationships – Graph exploration – Bipartite graph – Directed acyclic graph – Tree – Common problems in graph theory – Pathfinding, Spanning tree, Graph coloring, Topological sorting

Graphs in VLSI circuits and systems
Graphs as a VLSI abstraction tool- Register transfer level, Register allocation, Task scheduling, Synchronization, Gate layer – Ordered binary decision diagram, And-inverter graph, Circuit layer – Laplacian matrix of a circuit graph, Physicallayer -Partitioning, Floorplanning ,Placement, Routing

Synchronization in VLSI
Graph-based timing analysis -Timing constraints in synchronous systems, Clock skew scheduling – Robustness, Performance, Power, Clock tree synthesis – Clock tree topology, Clock tree embedding, Method of means and medians, Deferred merge embedding, Elmore delay, Bounded skew tree, Useful skew tree

Circuit analysis
Modified nodal analysis, Iterative numerical methods – Domain decomposition, H-matrix, Multigrid methods, Non-MNA techniques- Scattering parameters, Random walks, Lattice graph

Graph Theory in Logic Synthesis, Verification, and Emerging Trends
Graphs in Logic Synthesis- AND-Inverter Graphs (AIGs) for representing combinational logic. Technology Mapping-Graph covering problem, tree covering algorithms, Functional decomposition and factorization.
Verification Techniques – Critical Path Method (CPM) on DAGs for static timing analysis (STA), Longest path algorithms for slack calculation, Binary Decision Diagrams (BDDs): Graph representation of Boolean functions for equivalence checking and model checking, Satisfiability (SAT) Solvers: Graph-based formulations for design verification.
Emerging Trends – Graph Neural Networks (GNNs) in vlsi design, Quantum Circuit Graphs, Open-Source EDA Tools (ABC, Yosys)

References:
1. Logic Synthesis and Verification by Gary D. Hachtel, Fabio Somenzi
2. Graph Theory with Applications to Engineering & Computer Science by Deo Narsingh
3. Electronic Design Automation for IC Implementation, Circuit Design, and Process Technology by Lavagno, Luciano; Markov, Igor L.; Martin, Grant and Scheffer, Louis K
4. https://yosyshq.net/yosys/
5. https://people.eecs.berkeley.edu/~alanmi/abc/
6. “Graph Theory” by Reinhard Diestel
7. “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (CLRS)
8. Graphs in VLSI by Rassul Bairamkulov, Eby G. Friedman · 2022
9. Physical Design Automation of VLSI Systems by Sadiq M. Sait and Habib Youssef
10.Algorithms for VLSI Design Automation by Sabih H. Gerez