Computational Topology (M.Tech CS, 2026-27)
Computational Topology (M.Tech CS, 2026-27)
Instructors Arijit Ghosh
Status Ongoing
Description Introduction to computational topology
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
Lecture details
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:
Chapter 6 from [S18]
Topics covered in Lecture 2 (24 July 2026)
Class cancelled
Topics covered in Lecture 3 (29 July 2026)
Planar graph drawing and polygonal curves
Open sets, paths, and regions
Planar graphs and faces
Statement of the Jordan curve theorem and its limitations
Euler formula for planar graphs, and bounding number of edges in a planar graph
Reading materials:
Chapter 6 from [S18]