Past lectures
Geometric Representations of Graphs
Prof. Dr.
László
Lovász
Eötvös Loránd University
February 19 -
April 30, 2014
Date and time: Wednesdays, 13:15 - 15:00
Location: HG G 19.1
Resources
Background material (version 25.2.2014)Introductory example: the max cut problem
Rubber band representation I: Tutte's method
Rubber band representation II: Connectivity and harmonic functions
Coin representation
Square tilings
Orthogonal representations I: the theta-function
Orthogonal representations II: Minimal dimension
Second neighbor representation
Metric representations
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.