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.
|