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
[B+08] Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars, Computational Geometry: Algorithms and Applications, 3rd Edition, Springer, 2008
[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
[C51] Stewart S. Cairns, An elementary proof of the Jordan-Schoenflies theorem, Proceedings of the American Mathematical Society, 2: 860-867, 1951
[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
[D24] Reinhard Diestel, Graph Theory, 6th Edition, Springer, 2024
[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
[L17] Marc Lackenby, Topology & Groups, Lecture Notes, Oxford University, 2017
[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
[S93] John Stillwell, Classical Topology and Combinatorial Group Theory, Springer-Verlag, 1993
[S18] Benny Sudakov, Graph Theory, Lecture Notes, ETH Zurich, 2018
[T80] Carsten Thomassen, Planarity and duality of finite and infinite graphs, Journal of Combinatorial Theory, Series B, 1980
[T80] Helge Tverberg, A Proof of the Jordan Curve Theorem, Bulletin of the London Mathematical Society, 12(1): 34 - 38, 1980
[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:
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
Statement of Fáry's theorem for planar graphs
Euler formula for planar graphs, and bounding the number of edges in a planar graph
Reading materials:
Topics covered in Lecture 4 (31 July 2026)
Classification of Platonic Solids
Triangulating a simple polygon, and 3-coloring the triangulation
Art Gallery Problem
Reading materials:
Topics covered in Lecture 5 (5 August 2026)
Cancelled
Topics covered in Lecture 6 (7 August 2026)
Operations on graphs:
Vertex and edge deletion
Edge contraction
Edge subdivision
Graph minors and topological minors
Petersen graph, and the difference between graph minor and topological minor
Kuratowski graphs
Statements of Kuratowski's and Wagner's theorems on planar graphs
Proof of Wagner's theorem using Kuratowski's theorem
Reading materials:
Chapter 11 from [S18]
Topics covered in Lecture 7 (12 August 2026)
Class cancelled
Topics covered in Lecture 8 (14 August 2026)
Class cancelled
Topics covered in Lecture 9 (17 August 2026)
k-connectivity of graphs
Two structural results required for proving Kuratowski's theorem on planar graphs:
Edge contraction and 3-connected graphs
Kuratowski graphs and edge contraction
Reading materials:
Topics covered in Lecture 10 (19 August 2026)
General discussion on Jordan curve theorem and its consequences
Completed the proof of the Kuratowski theorem for planar graphs
Reading materials:
Topics covered in Lecture 11 (28 August 2026)
Proof of PL Jordan Curve Theorem
Properties of polygons: ear and frugal triangulation
Proof of PL Jordan-Schoenflies Theorem
Discussed the following theorems in complex analysis:
Riemann mapping theorem
Carathéodory's conformal mapping theorem
Reading materials:
Topics covered in Lecture 12 (2 September 2026)
Definitions of algebraic cycles, the cycle space of a graph and 2-basis of the cycle space
Statement of Mac Lane's planarity criterion
Properties of 2-connected graphs and 2-connected planar graphs
Block decomposition of graphs and block-cut tree
Proof that a graph is planar iff each block in the graph is planar
Reading materials:
Class handout
Topics covered in Lecture 13 (3 September 2026)
Properties of the cycle space of a graph:
Fundamental cycles
Dimension of the cycle space
Proof of Mac Lane's planarity criterion
Reading materials:
Class handout