Computational Topology (M.Tech CS, 2026-27)
Computational Topology (M.Tech CS, 2026-27)
Instructors Arijit Ghosh
Status Ongoing
Description Introduction to Computational Topology and Topological Data Analysis
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings TBA
Syllabus
Topological spaces
Simplicial complexes
Graphs in a plane:
Basics of planar graphs and Euler's formula
Crossing Lemma and Hanani-Tutte theorem
Planarity Testing
Faster algorithms in planar graphs
Planar separators and applications
Graphs on surfaces:
Classification theorem for surfaces
Algorithms for graphs on surfaces
Basics of homotopy
Homology
Chain complexes
Borsuk-Ulam Theorem and its applications
Persistent homology
Manifold learning
References
[AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016
[AZ14] Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK, Springer, 2014
[B21] Imre Bárány, Combinatorial Convexity, American Mathematical Society, 2021
[BCY18] Jean-Daniel Boissonnat, Frédéric Chazal and Mariette Yvinec, Geometric and Topological Inference, Cambridge University Press, 2018
[C21] Éric Colin de Verdière, Algorithms for Embedded Graphs, Lecture Notes, 2021
[DL21] François Dahmani and Francis Lazarus, Algorithmic Topology and Groups, Lecture Notes, 2021
[DW22] Tamal K. Dey and Yusu Wang, Computational Topology for Data Analysis, Cambridge University Press, 2022
[E14] Herbert Edelsbrunner, A Short Course in Computational Geometry and Topology, Springer, 2014
[EH10] Herbert Edelsbrunner and John L. Harer, Computational Topology: An Introduction, American Mathematical Society, 2010
[E23] Jeff Erickson, One-Dimensional Computational Topology, Lecture Notes, UIUC, 2023
[LT20] Francis Lazarus and Boris Thibert, Effective Methods in Geometry, Lecture Notes, ENS Lyon, 2020
[K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006
[L19] László Lovász', Graphs and Geometry, American Mathematical Society, 2019
[LM18] Francis Lazarus and Arnaud de Mesmay, Computational Topology, Lecture Notes, ENS Lyon, 2018
[M02] Jiří Matoušek, Lectures on Discrete Geometry, Springer, 2002
[M03] Jiří Matoušek, Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Springer, 2003
[N22] Vidit Nanda, Computational Algebraic Topology, Lecture Notes, University of Oxford, 2022
[PA95] Janos Pach and Pankaj K Agarwal, Combinatorial Geometry, Wiley-Interscience, 1995
[S22] Hal Schenck, Algebraic Foundations for Applied Topology and Data Analysis, Springer, 2022
[S18] Benny Sudakov, Graph Theory, Lecture Notes, ETH Zurich, 2018
[U15] Torsten Ueckerdt, Combinatorics in the Plane, Lecture Notes, KIT, 2015
Topics covered in Lecture 1 (22 July 2026)
Course introduction
Basic introduction to planar graphs
Proof that every graph can be embedded in 3-dimensional Euclidean space
Reading materials:
TBA
Topics covered in Lecture 2 (24 July 2026)
Class cancelled