max planck institut
informatik

# Seminar "Topological Optimization Problems" (Summer 2014)

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
DateSpeakerTopicFiles
15 AprilMichael + MichalPlan, distribution of topics
6 MayRafaella AntonyanPlanar graphs (intro topic 1)
13 MayRene NomanyoSurfaces (intro topic 2)
27 MayTiezhi WangShortest essential cycles (intro topic 3)Notes by RA
10 JuneAruni ChoudharyShortest path homotopic to a given path in polygonsNotes by CB
17 JuneCornelius BrandMinimum-length homotopy basis with a given basepointNotes by AN
24 JuneMichaelOptimal first homology basis on surfacesNotes by TW
1 JulyArnur NigmetovOptimal first homology basis on arbitrary complexesNotes by RN
8 JulyMichalComputing a canonical system of loops
Next:
22 July
Arijit GhoshLocalization over surfaces in Z_2
Introductory topics
1. Planar graphs, representation, MST, dual graph, separators
2. Surfaces, classification of surfaces, representations of embedded graphs (rotation systems, polygonal schemata, tree-cotree decomposition),
3. 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

For most topics, the survey by J.Erickson gives a good summary.
1. 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
2. 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
3. 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
4. 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
5. 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
6. 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
Resources

Search MPII (type ? for help)