*Note that this course is cross-listed with the ELTE University and is held on their campus. Its schedule is set by ELTE. Time and location will be available by the beginning of September*

*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.