Participants acquire in-depth knowledge about a current research topic in graph algorithms and computational geometry. Starting from selected original research papers, students independently perform literature research on related articles and obtain detailed and contextual knowledge about their topic. Through their seminar presentation and the written seminar paper students learn fundamtenal skills on presenting algorithmic research topics and scientific writing. By focusing the seminar on open research questions and research discussion the students acquire and expand their algorithmic problem solving skills. In particular, students learn and expand those skills that are also required for working on a Master's thesis in algorithmics.

Our seminar topics are in the areas of graph drawing and computational geometry and cover recent research questions.

Course structure

The seminar covers a recent theme in the area of graph drawing and graph algorithms. Following a general introduction into the topic students can choose their seminar topic from a list of suggestions. After two weeks they give a short presentation to introduce their topic to the seminar group. In November we will have the long presentations with subsequent discussions. In addition to the research results, presentations shall cover the remaining open research questions. In December we will discuss selected open problems in groups and develop solution strategies. Last year a joint publication originated from these research sessions.

The written seminar paper is due before the Christmas break, will be peer-reviewed and the final version is handed in in February.

ECTS breakdown

  5h introduction and topic selection
15h presentations and seminar meetings

25h work on seminar topic
10h preparations for presentation
20h seminar paper
----
75h

Attendance required

Oral presentation, written seminar paper, peer review, research session minutes.

• Mixed linear layouts of graphs (taken)
• Queue number of posets of bounded height or width
• Queue layouts of planar 3-trees
• Faster algorithms for some optimization problems on collinear points
• On contact graphs of paths on a grid
• Greedy rectilinear drawings (taken)
• How to fit a tree in a box (taken)
• The painter’s problem: Covering a grid with colored connected polygons (taken)

design and analysis of algorithms, in particular graph algorithms

basic geometry knowledge (high school level)