| Seminar time |
Tuesdays 16-18 |
| Room |
MPI 021
|
| Lecturers |
Michael Kerber and Michal Adamaszek
|
| Language |
English
|
| Description |
For many applications it is useful to have small descriptions of topological features. In this seminar we will look at algorithms for finding optimal representations of topologically "essential" information about triangulations of spaces, especially 2-dimensional surfaces. Suppose we start with a triangulated surface.
Now one may ask, for instance:
- Given a loop, find the shortest loop which is topologically equivalent to the given one (roughly: goes "around" the same holes in the same order as the given one; formally: is homotopic/homologous to the given one)
- Given a triangulation, find a shortest set of loops which generates the fundamental group or homology groups
We will start with introducing the necessary tools from topology and graph theory. The techniques involve a mix of geometry, graph algorithms and optimization.
|
| Literature |
To get some flavor of this area you may look at the lecture notes
|
| Prerequisites |
You should know about the basics of graph theory, including the concept of planar graphs and simple graph algorithms such as depth-first-search. Familiarity with topological notions such as surfaces, triangulations or homotopy may be of help, but is not essential.
|
| Credits |
To obtain credit for the course you must (i) give a presentation of the paper/topic assigned to you (approx. 1 hour) and (ii) write a short summary of someone else's talk.
You will also be required to make an appointment with one of the lecturers to discuss and practice your presentation ahead of your talk.
|
| Plan |
| Date | Speaker | Topic | Files |
| 15 April | Michael + Michal | Plan, distribution of topics | |
| 6 May | Rafaella Antonyan | Planar graphs (intro topic 1) | |
| 13 May | Rene Nomanyo | Surfaces (intro topic 2) | |
| 27 May | Tiezhi Wang | Shortest essential cycles (intro topic 3) | Notes by RA |
| 10 June | Aruni Choudhary | Shortest path homotopic to a given path in polygons | Notes by CB |
| 17 June | Cornelius Brand | Minimum-length homotopy basis with a given basepoint | Notes by AN |
| 24 June | Michael | Optimal first homology basis on surfaces | Notes by TW |
| 1 July | Arnur Nigmetov | Optimal first homology basis on arbitrary complexes | Notes by RN |
| 8 July | Michal | Computing a canonical system of loops | |
Next:
22 July | Arijit Ghosh | Localization over surfaces in Z_2 | |
|
| Introductory topics |
- Planar graphs, representation, MST, dual graph, separators
- Surfaces, classification of surfaces, representations of embedded graphs (rotation systems, polygonal schemata, tree-cotree decomposition),
- Shortest non-contractible and non-separating cycles on surfaces
- de Verdiere, Chapter 4 (and the necessary prerequisites from chapter 3)
- (as an alternative, or supplement) Erickson Section 8
|
| Advanced topics |
For most topics, the survey by J.Erickson gives a good summary.
- Shortest path homotopic to a given path in polygons
-
John Hershberger, Jack Snoeyink: Computing minimum length paths of a given homotopy class. Computational Geometry, Volume 4, 1994, pp. 63-97 (pdf)
- Survey, Section 4.1
- Minimum-length homotopy basis with a given basepoint
-
Jeff Erickson, Kim Whittlesey: Greedy optimal homotopy and homology generators. SODA 2005, pp. 1038-1046 (pdf)
-
Eric Colin de Verdiere: Shortest Cut Graph of a Surface with Prescribed Vertex Set. ESA 2010, pp.100-111 (pdf)
- Survey, Section 3.2
- Computing a canoncical system of loops
-
Francis Lazarus, Gert Vegter, Michel Pocchiola, Anne Verroust: Computing a Canonical Polygonal Schema of an Orientable Triangulated Surface. SoCG 2001, pp. 80-89 (pdf)
- Survey, Section 3.3
- Optimal first homology basis on surfaces
-
Jeff Erickson, Kim Whittlesey: Greedy optimal homotopy and homology generators. SODA 2005, pp. 1038-1046 (pdf)
- Tamal Dey, Jian Sun, Yusu Wang: Approximating Loops in a Shortest Homology Basis from Point Data. SoCG 2010, pp.166-175 (pdf)
- Survey, Section 6.1
- Optimal first homology basis on arbitrary complexes
- Chao Chen, Daniel Freedman: Measuring and computing natural generators for homology groups. Computational Geometry, Volume 43, 2010, pp. 169-181 (pdf)
- Tamal Dey, Jian Sun, Yusu Wang: Approximating Loops in a Shortest Homology Basis from Point Data. SoCG 2010, pp.166-175 (pdf)
- Survey, Section 6.2
- Localization over surfaces in Z_2
- Jeff Erickson, Amir Nayyeri: Minimum cuts and shortest non-separating cycles via homology covers. SODA 2011, pp. 1166-1176 (pdf)
- Gross, Tucker: Topological Graph Theory. ISBN-13: 978-0486417417
- Survey, Section 7
|
