Abstract.
To represent a graph geometrically is a natural goal in itself, but in addition it is an important tool in the study of various graph properties, including their algorithmic aspects. There are several levels of this interplay between algorithms and geometry.
Often the aim is to find a way to represent a graph in a "nice" way. For example, we want to draw a planar graph in the plane without intersections, with straight edges, with convex faces, etc. Many difficult algorithmic problems in connection with finding these representations have been studied.
In other cases, graphs come together with a geometric representation, and the issue is to test certain properties, or compute some parameters, that connect the combinatorial and geometric structure. A typical question in this class is rigidity of bar-and-joint frameworks, an area whose study goes back to the work of Cauchy and Maxwell.
Most interesting are the cases when a good geometric representation of a graph not only gives a useful way of visualizing its structure, but it leads to algorithmic solutions of purely graph-theoretic questions that, at least on the surface, do not seem to have anything to do with geometry. This course will cover several examples of this (the list is far from complete): rubber band representations in planarity testing and graph drawing; repulsive springs in approximating the maximum cut; coin representations in approximating optimal bisection; nullspace representations for Steinitz representations of planar graphs; orthogonal representations in algorithms for graph connectivity, graph coloring, finding maximum cliques in perfect graphs, and estimating capacities in information theory; volume-respecting embeddings in approximation algorithms for bandwidth.
Time: Wednesday 13-15 on Feb. 19, 26, on March 12, 19, 26, and on April 2, 9, 16, 30;
Friday 13-15 on March 21, March 28 and April 11.
Auditorium: HG G 19.1 (except March 19; see separate announcement)
Begins: February 19
M. Struwe