COMP 7750 - fall 2016

COMP 7750 - Graph Drawing

COMP 7750: A graduate course in graph drawing: the design and analysis of efficient algorithms for drawing a given graph in the plane subject to given constraints and optimization criteria.

instructor: Steph Durocher
office hour: 9:00 am on Tuesday in EITC E2-412.

lectures: 10:00 - 11:15 am on Tuesday and Thursday in EITC E2-360.

This calendar lists course-related events for COMP 7750:

Although also numbered COMP 7750, this course on graph drawing differs from COMP 7750: Computational Geometry. In particular, students who have completed COMP 7750 (Computational Geometry) for credit can also take COMP 7750 (Graph Drawing) for credit.

Prerequisites

Students are expected to have a strong background in theoretical computer science (e.g., A or A+ in COMP 3170). Students will be required to complete a mandatory quiz during the first week of classes to help determine whether they possess the required background. Quiz marks will not count towards course grades, but students are required to pass the quiz to continue in the course. There is no need to study any specific material before the quiz.

The formal course requirements are:

  • an upper-level undergraduate course in algorithms analysis and data structures such as COMP 3170
  • a course in discrete mathematics such as COMP 2130

Reference Textbooks

Graph Drawing: Algorithms for the Visualization of Graphs by di Battista, Eades, Tamassia, and Tollis, Prentice Hall, 1999.

Planar Graph Drawing by Nishizeki and Rahman, World Scientific, 2004

Handbook of Graph Drawing and Visualization by Tamassia (editor), CRC Press, 2013

Topics Covered

Topics will include:
  • graph drawing conventions
  • drawing trees
    • rooted trees
    • k-trees
    • outerplanar graphs
    • series-parallel graphs
  • drawing layered graphs
  • planarity testing
  • drawing planar graphs
    • straight-line drawings
    • convex drawings
    • orthogonal drawings
    • visibility drawings
    • contact graph representation
  • point-set embeddings
  • applications
See this course outline for a more detailed course description.

Announcements

The project schedule is available.

The final exam will be held 10:00 am - 12:00 pm on Thursday, December 15, in EITC E2-304.

last updated November 16, 2016

Important Dates

Nov 24assignment 3 due
Nov 29project presentations begin
Dec 8project final report due
Dec 8last class
Dec 15final exam 10:00 am - 12:00 pm
Dec 22exams end