Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Seminar Geometry: Combinatorics and Algorithms FS18 (263-4203-00L)

Luis Barba, CAB G33.3, Tel: 044-632 77 96,
Michael Hoffmann, CAB G33.1, Tel: 044-632 73 90,
Pavel Valtr, CAB G19.2,
Emo Welzl, CAB G39.2, Tel: 044-632 73 70,


This seminar is held once a year and complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area.

To attend the seminar, some background in (discrete and computational) geometry and in graphs and algorithms is required. Thus, previous participation in the course "Geometry: Combinatorics & Algorithms" is a prerequisite.


First meeting: Friday Feb 23rd 2018, 13:15, CAB G15.2.


All talks in CAB G15.2.

Topic and Papers

The title of the seminar is Intersections: Models, Representations & Algorithms.

Intersection graphs are defined on a collection of geometric objects that represents the set of vertices. There is an edge between two vertices if their corresponding geometric objects intersect. These graphs appear naturally in many combinatorial and computational problems. Depending on the class of geometric objects used to define them (segmens, circles, convex objects, curves), the induced intersection graph can have quite interesting and particular properties. What is their chromatic number, the size of their largest clique, or the size of their maximum independendt set? Another line of research is to ask which graphs are intersection graphs, and for which geometric objects can we recognize these graphs? What is the complexity of the objects needed to represent these graphs?


The seminar is held in English. Each talk is 45min. plus about 15min. discussion.
Every participant is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes
  1. getting an overview of the related literature;
  2. understanding and working out the background/motivation: why and where are the questions addressed relevant?
  3. understanding the contents of the paper in all details;
  4. selecting parts suitable for the presentation;
  5. presenting the selected parts in such a way that an audience with some basic background in geometry and graph theory can easily understand and appreciate it.

For more details, please refer to our guidelines for seminar talks. A number of additional related documents from different authors (both in English and German) are linked to from here.

A successful participation in the seminar requires the following:

  1. a rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
  2. a satisfactory plenary talk;
  3. attendance at all other talks.

Last modified: Tue Feb 13 18:42:43 CET 2018 by Michael Hoffmann. Valid HTML 4.0!