Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Graph Drawing (252-4206-00L) FS10

 

Time & Place

Lecture: Monday 10:15-12:00 CAB G51. The lecturers are:
Bernd Gärtner, CAB G31.1, Tel: 044 632 70 26, .
Michael Hoffmann, CAB G33.1, Tel: 044 632 73 90, .
Exercise: Monday 13:15-14:00, CAB G59. The teaching assistant is:
Marek Sulovský, CAB G32.1, Tel: +41-44-632 80 75, .
 

Contents

 

Course Material

Date Content Exercises Lecture notes and links
#1 (22.02.2010) General Introduction Exercise 1 Introduction   Planarity
#2 (1.3.2010) LR planarity test Exercise 2 LR test
#3 (8.3.2010) LR partition Exercise 3,
Homework 1 		LR partition
#4 (15.3.2010) Fáry's Theorem and Tutte's spring embeddings Exercise 4 Tutte
#5 (22.3.2010) Crossing lemma and point-line incidences Exercise 5 see lecture notes of M. Smid or Lectures on Discrete Geometry by J. Matousek.
#6 (29.3.2010) Grid embeddings Homework 2 theorem by Thomassen
#7 (12.4.2010) Grid embeddings (shift algorithm) Exercise 6 Section 4.2 in Nishizeki/Rahman or the original papers by de Fraysseix et al. and Chrobak/Payne
#8 (19.4.2010) Map labellings Homework 3 paper by Formann/Wagner
#9 (26.4.2010) Trees lecture notes
#10 (3.5.2010) Rectangular drawings and cartograms Section 6.2 in Nishizeki/Rahman and slides
#11 (10.5.2010) Orthogonal drawings Homework 4
#12 (17.5.2010) Orthogonal drawings and Q&A Solution slides: 6.2b, 6.3
#13 (31.5.2010) Orthogonal drawings Exam questions - theory
 

Course Description

Graph Drawing is concerned with embeddings of graphs, mostly into the Euclidean plane.

The goal is to make students familiar with the important techniques and results in graph drawing, and to enable them to attack theoretical and practical problems in various application domains.

Fundamental questions of interest are: Which properties are desirable for a drawing? Under which conditions do certain types of drawings exist and can these conditions be tested for efficiently? Can a certain type of drawing be constructed efficiently? We will discuss some of the important directions and results of the area, a few classic and others more recent.

Possible topics include planarity testing, plane embeddings (Tutte's Theorem), Schnyder woods, Crossing Lemma, grid embeddings, map labeling, and orthogonal drawings.

 

Procedures, exercises, exam

Every week we provide you with an exercise sheet. You should solve it in written form and return your solutions the week after. Your solutions are thoroughly commented and graded, but they do not count towards your final grade. The motivation to work on the exercises stems from your interest in the topic (and possibly also the desire to succeed in the exam :-)).

In Addition, you receive four small projects during the semester. Also these projects are to be solved in written form, but typically you have two weeks of time to return your solutions/reports, typeset in LaTeX. In contrast to the exercises, projects do count towards the final grade: Your three best grades will account for 10% of your final grade each. Solving projects in teams is not allowed.

There is an oral exam of 30 minutes during the examination period. Your final grade consists to 70% of the grade for the exam and to 30% of the grade for the projects.

You are expected to learn proofs discussed in the lecture, should be able to explain their basic ideas and reproduce more details on demand. You should also be able to give a short presentation on any topic treated throughout the course.

One of the questions given to you during the exam is to solve one of the exercises posed throughout the semester.

Roughly half an hour before the exam you get to know the exercise to be solved and one topic that you will be questioned about in particular, that is, you have 30 minutes preparation time. For this preparation, paper and pencil will be provided. You may not use any other material, like books or notes.

For PhD students, the same rules apply for obtaining credit points as for all other participants. Taking the exam and achieving an overall grade of at least 4.0 (computed as a weighted average of grades for special exercises and the written final exam as detailed above) qualifies for receiving credits. In order to comply with new regulations recently issued by the department, merely attending the course and/or handing in exercises is no longer sufficient.

 

Complementary Courses & Semester/Master/Diploma Theses

 

Literature and Links