Department of Information and Computing Sciences

Departement Informatica Onderwijs
Bachelor Informatica Informatiekunde Kunstmatige intelligentie Master Computing Science Game&Media Technology Artifical Intelligence Business Informatics

Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Graph drawing

Website:website containing additional information
Course code:INFOGDR
Credits:7.5 ECTS (=5.25 old credit points)
Period:period 1 (week 36 through 45, i.e., 8-9-2005 through 11-11-2005; retake week 1)
Participants:up till now 15 subscriptions
Schedule:Dit is een oud rooster!
college   Wed 13-1537-44 BBL-420
Fri 11-1336-44 BBL-420
seminar          Hans Bodlaender
Marc van Kreveld
Contents:In many applications, one wants to draw graphs or networks on the plane, e.g., when displaying graphs on a computer screen or when realizing chip layouts or electronic circuits. Different applications pose different requirements from such a diagram: sometimes we want to be a diagram to be compact, and sometimes we want that the diagram is pleasant to the human eye: the latter requirement seems hard to formalize. There are also different types of drawings: e.g., edges may be represented by curves, straight lines, or lines with angles. It also makes a difference whether the graph is planar (can be drawn without crossings) or not.
In this seminar, we look to a number of algorithms for drawing graphs and study aspects of their quality.
Literature:There is no obligatory book for the course. Recommended books are:
  • Planar Graph Drawing. Takao Nishizeki and Md. Saimur Rahman. Lecture Notes Series on Computing - vol 12, 2004.
  • Graph Drawing: Algorithms for the Visualization of Graphs Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ionannis G. Tollis Prentice Hall, 1998, ISBN 0133016153
The course will also use scientific papers, including papers from recent proceedings of the yearly Graph Drawing conferences.
Course form:Seminar. The book and papers will be studied together, and students will give 2 lectures about chapters of the book or studied papers. Students write a survey on the topic of the second lecture.
Exam form:There is no written exam. The end note is: 30 percent: presentation 1; 30 percent: presentation 2; 30 percent: survey; 10 percent: participation etc. Participation must be sufficient. All three other notes should be at least 5; one task can be done as 2nd chance.
Minimum effort to qualify for 2nd chance exam:Active participation; presence during the sessions; note of at least 5 for two out of the three tasks. The 2nd chance exam means that one task (lecture 1, lecture 2, survey) can be done again.