Seminar: Geometry, Graphs and Algorithms
Winter semester 2019
General Information
- Seminar meeting: Friday 9:45 Uhr, SR236 (Informatics building 50.34)
- First meeting: Friday, 18.10., 9:45 Uhr, SR236 (Informatics building 50.34)
- Credits: 4LP
- Module: M-INFO-102550
- Registration: Via email to Torsten Ueckerdt or to Dr. Tamara Mchedlidze (please include your „Matrikelnummer“). The number of participants is limited.
- Language: The seminar will be held in English
Content
Graphs and networks model realworld situations and often the graph defining structures are geometric. This makes a tailored treatment of geometrically defined graph classes an important branch of research, both theoretically and practically. For example, road networks give rise to almost planar graphs, job schedules give rise to intersection graphs of intervals, or DNA sequences give rise to graphs with a linear ordering on their vertices. On the other hand, geometry can be intentionally inferred to graphs for visualization purposes.
In this seminar, we discuss a wide range of geometric settings for graphs and combinatorial problems. Topics include among others the existential theory of the reals, VC-dimension, machine learning, planarization, and visualization.
Procedure
At the first, preliminary meeting, the topics will be briefly presented and assigned to the participants. Afterwards each participant explores their topic using the given literature as a starting point. After a couple of weeks each participant gives a 5-minute short presentation on their topic. During the semester we will then have the main presentations on separate days. By the end of the semester and after a peer review phase, each participant has to hand in a written report of 12–15 pages in LaTeX. The overall grade depends equally on the main presentation and the written report.
Schedule (tentative and subject to change)
| Date | Schedule | Speaker |
|---|---|---|
| 18.10. | Introduction (slides) and Topic Distribution | Tamara, Torsten |
| 8.11. | Short presentations | all students |
| 29.11. | Attention, Learn to Solve Routing Problems! | Tobias |
| 6.12. | Exploiting Air-Pressure to Map Floorplans on Point Sets | Laurin |
| Planar Graphs have Bounded Queue Number | Adrian | |
| 13.12. | Untangling Planar Curves | Michael |
| GosperMap: Using a Gosper Curve for Layering out Hierarchical Data | Yue | |
| 20.12. | The Complexity of Drawing a Graph in a Polygonal Region | Charel |
| The Complexity of Simultaneous Geometric Graph Embedding | Nadine | |
| 24.1. | Submission of the document | - |
| 21.2. | Submission of the reviews | - |
| 20.3. | Submission of the final document | - |
Remarks
- Please use LaTeX for composing the written report with this template:template.zip.
- Tips & Tricks for presentations an scientific writing.
- Information on using ipe for figures und presentations.