April 2016 CSE6410: Advanced Algorithmic Graph Theory

Vertex Orderings: st-Numbering and Canonical Orderings; Graph Decompositions and Their Algorithmic Applications: Ear Decomposition, Canonical Decomposition, Tree Decomposition, Path Width and Tree Width, PQ-tree, SPQR-tree, Split Decomposition, Recursively Decomposable Graphs, Clique Separator Decomposition; Graph Representations: Implicit Representations, Intersection and Containment Representations; Graph Classes Defined by Forbidden Subgraphs; Graph Classes Defined by Elimination Schemes; Classes of Graphs with Bounded Treewidth and Their Algorithmic Implications; Characterization, Construction and Recognition Algorithms for Some Special Classes of Graphs.