Advanced Seminar A (202-2-1511)

Graph Drawing

Fall 2008-9



Matya Katz  (

Office hours: Wednesday 14:00-16:00, Alon building (37), room 212, Tel: (08) 6461628


Class Time:

Tuesday 18-20


Course Description:

Graphs are often used to represent information that can be modeled as objects and connections between those objects. A drawing of a graph G is a pictorial representation of G, where points and arcs are usually used to represent the vertices and edges of G. Many information visualization systems generate graph drawings. These drawings should be easy to read and understandable. The course deals with algorithmic techniques for the construction of graph drawings. The study of such techniques constitutes an active research field known as graph drawing, with its own annual symposium, etc.


Main textbook:

Graph Drawing: Algorithms for the Visualization of Graphs, Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis, Prentice Hall, 1999, ISBN: 0-13-30-1615-3

Some necessary background can be found here:

Computational Geometry: Algorithms and Applications (3rd edition),
M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Springer-Verlag, 2008,
ISBN: 978-3-540-77973-5


This is a 1-credit course.

Students are required to attend all lectures.

Each student will give a lecture. In addition several homework assignments and short quizzes are expected.

Student Presentations:

Liana Diesendruck (based on Chapter 2)

Chen Shay (based on Chapter 3, Section 3.1)

Eran Geva (based on Chapter 3, Sections 3.1,3.2)

Tomer Heber (based on Chapter 4, Sections 4.14.6)

Victor Makarenkov and Olga Maksin (based on Chapter 4, Sections 4.74.10)

Nimrod Milo and Ilan Orlov (based on Chapter 5)

Ami Hauptman and Masha Igra (based on Chapter 6)


Last update January 12, 2009.