The theory of intersection graphs will soon have, together with others, an own matematics subject classification number 05C62. This promotion may be mainly due to the fact that intersection graphs have nice applications---some of them even originated in such applications. Although a large amount of work has been done for several intersection graph models, there are still only very few basic concepts and ideas which work for general intersection graphs, and even these ideas are not as widely known as they maybe should. So let me introduce 05C62, at least the intersection graph part, to you.
The intersection graph of a system (Sx, Sy, Sz, ...) has vertices x,y,z,.... Two distinct vertices x,y are joined by an edge whenever Sx and Sy have nonempty intersection.
In the simplest case of a fixed model, all these sets Sx must have a certain shape, for instance be circles in the plane. Then we concentrate on all possible intersection graphs of such sets.
Most models of the literature are variants or generalizations of the classical examples of line graphs or interval graphs. Either we consider intersection graphs of finite sets, and call the models discrete. One typical example is that all sets have to have equal size. In another classical problem one has no further restriction but tries to minimize the size of the union of all sets. In geometrical models, we consider intersection graphs of subsets of Rd with some geometric property. Then often geometrical or order tools come into play.
What are the natural questions for classes of intersection graphs? Recognition is the question of whether a given graph is the intersection graphs of sets of our shape. In application it is often important to find certain large substructures in the intersection graphs occuring, see this or this or this example. Im many cases this means finding some parameters of the intersection graphs. Finding largest cliques turn out to be treatable for certain intersection graph models, whereas other parameters mostly remain hard.
You may want to start with examples or with the origins of intersection graphs. The most important tool for intersection graphs is duality. What makes certain classical models tractable is the so-called Helly-property. By duality, intersection graphs should be viewed as the union of certain complete subgraphs---if we have the Helly-property, these complete subgraphs are really (maximal) cliques.
Certain topics are not appropriate for the start: There are certain topological results on intersection graphs for which you need some knowledge on duality and the Helly property. A section on random models treats some properties and it is shown how certain intersection graphs where recognition is NP-complete, can actually be recognized almost surely.
There are also some variants, which you may not want to visist at the beginning. For instance, by only recognizing intersections of a certain size we arrive at t-intersection---for discrete models, or tolerance intersection--- for geometric models. If we know for each pair of sets in a discrete model the size of the intersection, we get intersection multigraphs. There are also variants of intersection graphs for bipartite graphs or digraphs---you just need families of pairs of sets. Connection graphs are essentially underlying (undirected) graphs of intersection digraphs.
Here is a table of contents:
T.A. McKee and F.R. McMorris [MM99] published quite recently a monograph on intersection graphs, which covers some of the topics presented here in more detail. M. Golumbic`s classical book [G80], though old and not focussing primarily on intersection graphs, is still a valuable source for many intersection graph classes. An up to date survey on graph classes by A. Brandtstädt, V.B. Le and J. Spinrad will appear next month in the same SIAM series than [MM99].
This is the WWW-version of a survey that I wrote for and partially during a stay at Santiago de Chile, as script for some minicourse held there in June/July 1998. I am very grateful for the support received by FONDAP and for the hospitality of the Universidad de Chile. I am also indepted to Dieter Kratsch, Haiko Müller, and Van Bang Le for useful remarks on an earlier draft of this "paper".