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
*(S _{x}, S_{y}, S_{z}, ...)* has
vertices

In the simplest case of a fixed model, all these sets
*S _{x}* 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
**R ^{d}** 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:

- Motivating Examples
- Origins:
- Duality, Helly-property, Topological results
- Cliques
- Intersection number

- Recognition and Reconstruction
- Optimization in intersection graphs

- Order
- Uniform hypergraphs
- Clique Graphs
- Intersection Classes
- Random models
- Distance

- t-intersection
- Tolerance intersection
- Intersection multigraphs
- Intersection bi- and digraphs
- Connection graphs
- Intersection
*h*-graphs

- Definitions
- Bibliography
- Index

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

Erich Prisner

made on January 12, 1999, last update on March 24, 1999.