Instructor: Dr. László Lovász
This course is intended for Master's students. The language of instruction is English.
This semester the main topic is Geometric representations of graphs.
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.
Often the aim is 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. 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 proofs or algorithmic solutions of purely graph-theoretic questions. Examples (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 polyhedra 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. This course will cover as many of these as time permits.