CPSC 536E Graph Drawing Fall 2023

Professor:
William Evans, ICCS X841, 822-0827, e-mail: will@cs.ubc.ca, home page: www.cs.ubc.ca/~will/,

Lectures:
T Th 11.00-12.30 SWNG 208
01 Introduction
02 Determining Planarity Left-Right Planarity Test
03 Canonical Ordering
04 Schnyder woods
05 Tutte embedding Graphs and Geometry [Lovász]
06 Spring embedding with repulsion [Eades 1984] [Fruchterman & Reingold 1991]
07 Graph-distance preserving embedding [Kamada & Kawai 1984] Minature 7: Are These Distances Euclidean? [Matoušek] Lectures on Discrete Geometry Chapter 15: Embedding Finite Metric Spaces into Normed Spaces [Matoušek] [Klimenta & Brandes 2012] [Brandes & Pich 2007]
08-10 Rectangle and Square Representation Rectangle and Square Representations of Planar Graphs [Felsner] Square tilings with prescribed combinatorics [Schramm] Graphs and Geometry (Chapter 6: Square Tilings)[Lovász] Blocking and anti-blocking pairs of polyhedra [Fulkerson]
11&12 Orthogonal Graph Drawing On embedding a graph in the grid with the minimum number of bends [Tamassia] Planar grid embedding in linear time [Tamassia & Tollis]
Map Labelling A packing problem with applications to lettering of maps [Formann & Wagner] Label placement by maximum independent set in rectangles [Agarwal, van Kreveld, & Suri] A note on maximum independent sets in rectangle intersection graphs [Chan]

Homework:
Homework 1
Homework 2

Course Description:

Graph drawing is about the representation of graphs using geometric objects. For example, we might draw a graph using dots in the plane to represent vertices and line segments connecting pairs of dots to represent edges between vertices. Or we might draw the vertices as horizontal segments in the plane such that two vertices are adjacent if and only if their segments have an uninterrupted vertical line of sight between them.

We will talk about techniques for drawing graphs and properties of graphs that permit or forbid certain representations. We will consider what properties of a representation are desirable, what algorithms exist to achieve these properties (or decide they cannot be achieved) efficiently, and when such efficient algorithms are unlikely to exist.

Possible topics include planarity testing, force-directed embedding, map labeling, edge bundling, Schnyder woods, contact representation, and visibility representation.

The course has no textbook, however, some of the material for the course will come from the

[Handbook] Handbook of Graph Drawing and Visualization.

Other good resources are:

[DETT] Graph Drawing - Algorithms for the Visualization of Graphs by Di Battista, Eades, Tamassia, and Tollis. (on reserve at the CS Reading Room)
[KW] Drawing Graphs - Methods and Models by Kaufmann and Wagner.
[Felsner] Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry by Felsner.
[NR] Planar Graph Drawing by Nishizeki and Rahman (on reserve at the CS Reading Room)

Prerequisites:

The course is intended for students with a basic understanding of algorithms, data structures, and graphs.

Evaluation:

Students will be required to do an in class presentation of an approved project of their choice. The project might be, for example, an implementation, a literature exploration, a solution to a theoretical problem, or a potential submission to the graph drawing contest associated with the International Symposium on Graph Drawing. The project and presentation will contribute 50% to the final grade. In addition, there will be occasional homework exercises with some required reading (25%), and class participation (25%), which includes typesetting notes for one or two lectures so that they may be distributed to the rest of the class.