Instructor: Dr. László Lovász
Course description:
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.