Computational Topology - An Introduction

Table of Contents

Part A

I Graphs 1
1 Connected Components 2
2 Curves in the Plane 9
3 Knots and Links 15
4 Planar Graphs 22
Exercises 29

II Surfaces 31
1 Two-dimensional Manifolds 32
2 Searching a Triangulation 39
3 Self-intersections 45
4 Surface Simplification 51
Exercises 57

III Complexes 59
1 Simplicial Complexes 60
2 Convex Set Systems 67
3 Delaunay Complexes 74
4 Alpha Complexes 81
Exercises 88

Part B

IV Homology 91
1 Homology Groups 92
2 Matrix Reduction 98
3 Relative Homology 104
4 Exact Sequences 111
Exercises 118

V Duality 121
1 Cohomology 122
2 Poincar´e Duality 128
3 Intersection Theory 132
4 Alexander Duality 136
Exercises 139

VI Morse Functions 141
1 Generic Smooth Functions 142
2 Transversality 148
3 Piecewise Linear Functions 154
4 Reeb Graphs 160
Exercises 167

Part C

VII Persistence 169
1 Persistent Homology 170
2 Efficient Implementations 178
3 Extended Persistence 184
4 Spectral Sequences 191
Exercises 198

VIII Stability 201
1 Time Series 202
2 Stability Theorems 208
3 Length of a Curve 215
4 Bipartite Graph Matching 221
Exercises 228

IX Applications 231
1 Image Segmentation
2 Elevation
3 Gene Expression
4 Local Homology for Plant Root Architecture
Exercises

Part D

X Open Problems 237
1 Complexity of Reidemeister Moves 238
2 Shelling a 3-ball 239
3 Geometric Realization of 2-manifolds 241
4 Embedding in Three Dimensions 242
5 Equipartion in Four Dimensions 243
6 Running-time of Matrix Reduction 244
7 Multi-parameter Persistence 245
8 Unfolding PL Critical Points 246
9 PL in the Limit 247
10 Counting Halving Sets 248

Index 259