|02 Determining Planarity||Left-Right Planarity Test|
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)|
The course is intended for students with a basic understanding of algorithms, data structures, and graphs.
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.