Syllabus
NP-hardness of recognition (intersection graphs of segments, convex sets and strings).
Sizes of representation (graphs requiring representations of exponential size).
Representability of planar graphs (Koebe's theorem on touching circles, bipartite graphs as visibility graphs).
Bounds on chromatic number as a function of the clique number.
Drawing planar graphs on a fixed point set. 3-dimensional graph representation.
Annotation
Advanced course in Computer Science
Intersection and contact representations of graphs, including interval graphs, chordal graphs, circle graphs, circular-arc graphs, segment-intersection graphs, string graphs. Characterization theorems, NP-hardness results for recognition.
Sizes of representations. Optimization algorithms for classes of intersection graphs. Representations of planar graphs (kissing lemma, visibility representations, drawing on small size grid).