VL25401 Graph Theory for VLSI Engineers – Semester IV – VLSI – R-2025

Subject Code & Name: VL25401 – Graph Theory for VLSI Engineers

Regulation: R-2025

Semester: IV (Fourth Semester)

Branch: B.E. Electronics Engineering (VLSI)

Credits / L-T-P: 3 Credits | L-T-P: 3-0-0

Course Objectives

• 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.

Full Unit-wise Syllabus

Unit I – 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

Unit II – 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, Synchronization in VLSI Routing Floorplanning,Placement, 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

Unit III – Circuit analysis

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

Unit IV – 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)

Course Outcomes (COs)

• CO1: Understand fundamentals of graph theory and graph representations used in VLSI systems.
• CO2: Model VLSI circuits using graph structures such as DAGs, AIGs, BDDs, and hypergraphs.
• CO3: Apply graph algorithms for VLSI design tasks such as partitioning, placement, routing, and scheduling and graph-based techniques in logic synthesis, verification, and emerging EDA trends.
• CO4: Analyze timing, synchronization, and clock tree structures using graph-based methods in VLSI systems.

Source: Official Anna University – B.E. Electronics Engineering (VLSI Design and Technology) R-2025 Syllabus
Last Updated: October 2026