Graphs, Geometry, and Algorithms

''Studienleistung'': at least 50 percent of the homework points, small presentation.
''Prüfungsleistung'': Oral or written exam.

Graphs appearing in applications often come with a given geometric embedding in space or with the desire of a nice representation. This results in many interesting problems in the interplay of graphs and geometry which we study from an algorithmic point of view.

We study different geometric representations, the algorithmic complexity of computing such representations or deciding whether such a representation exists. We will understand how such representations may help to solve otherwise difficult problems and are capable of developing algorithmic methods for new problems.

1. visualizing planar graphs (straight-line drawings, contact representations, face areas, ...)
2. coloring (Ringel's Circle problems, coin problem, circle problem, intersection graphs and chi-boundedness )
3. recognition complexity (planarity testing, minor-closed graph classes, contact and intersection graphs, hypergraph realizations)
4. further case studies from current research

This class will be held in English. Students are encouraged (but not required) to use English in exercises and exams as well.

1. Michael Kaufmann, Dorothea Wagner: Drawing Graphs: Methods and Models.
2. T. Nishizeki, N. Chiba: Planar Graphs, Theory and Algorithms
3. Tamassia: Handbook of Graph Drawing and Visualization
4. G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing, Algorithms for the Visualization of Graphs.
5. Relevant research articles