2IMG00 - Seminar Applied Geometric Algorithms - Fall 2015 2016-10-28.

go directly to the schedule

Announcements:

10/11/2015 The first class of the Applied Geometric Algorithms seminar (2IMG00) will be on Friday, 13/11/15 (in META FORUM 14). The Wednesday, 11/11/15 class is cancelled.

We meet on:

Instructors:

Dr. Kevin Verbeek, MF 4.106, k.a.b.verbeek@tue.nl
Dr. Irina Kostitsyna, MF 4.103,

Course Description

This seminar focuses on one specific area in the field of applied algorithms, namely graph drawing. Graphs are widely used to represent information that can be modeled as objects and connections between those objects. By drawing these graphs automatically we can effectively visualize this information, which finds application in, for example, cartography, sociology, software engineering, and VLSI design. A typical graph drawing algorithm strives to lay out a graph while satisfying certain aesthetic criteria: minimize the number of edge crossings, separate vertices and edges so that they can be distinguished visually, preserve properties like symmetry and distance, to name a few. This seminar covers basic graph drawing concepts and algorithms.

The students will complete two assignments: a background literature study, and a choice of programming or research project. For the literature study, the students will explore a specific topic of graph drawing. Starting with an initial selection of literature provided by the instructors, they will find more literature, learn about the existing research results and open problems, and summarize the acquired knowledge in an overview presentation. For the second assignment, the students will choose a small research project which will either be mostly theoretical or also involve applied (programming) aspects.

Prerequisites:

At least one and preferably two of the courses Advanced Algorithms (2IL45), Geometric Algorithms (2IL55) and Algorithms for Geographic Data (2IL76) is required.

Format:

The final grade will be based on two items:

  1. One presentations of 45 min. which counts for 50% of the final grade.
  2. The results of the programming or research project which counts for the remaining 50% of the final grade.

All participants are expected to prepare for and take part in discussions during and after the presentations given by the other participants. Attendance is mandatory. If you find that you absolutely can not attend a particular meeting, you have to contact us at least 48 hours before. Unexcused absence will reflect negatively upon your final grade.

Topics:

1 Planarity testing 7 Hypergraph drawings and set visualization
2 Contact representations 8 Confluent drawings
3 Flow and orthogonal drawings 9 Proximity drawings
4 Straight-line planar drawings with small area 10 Graph coloring
5 Crossing minimization 11  
6 Simultaneous embeddings 12  

Schedule:

DateTimeLecturerTopicSlidesMaterial
11/11/201515:45—17:30
13/11/201510:45—12:30
18/11/201515:45—17:30
20/11/201510:45—12:30
25/11/201515:45—17:30
27/11/201510:45—12:30
02/12/201515:45—17:30
04/12/201510:45—12:30
09/12/201515:45—17:30
11/12/201510:45—12:30
16/12/201515:45—17:30
18/12/201510:45—12:30
 
06/01/201615:45—17:30
08/01/201610:45—12:30
13/01/201615:45—17:30
15/01/201610:45—12:30

Literature:
   
   
last modified: 05-Oct-2015  
contact: Kevin Verbeek