Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.

For an overview of both the theory of intersection graphs and important special classes of intersection graphs, see McKee & McMorris (1999).

Formally, an intersection graph is an undirected graph formed from a family of sets

by creating one vertex v_i for each set S_i, and connecting two vertices v_i and v_j by an edge whenever the corresponding two sets have a nonempty intersection, that is,

Any undirected graph G may be represented as an intersection graph: for each vertex v_i of G, form a set S_i consisting of the edges incident to v_i; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge. Erdős, Goodman & Pósa (1966) provide a construction that is more efficient (which is to say requires a smaller total number of elements in all of the sets S_i combined) in which the total number of set elements is at most n²/4 where n is the number of vertices in the graph. They credit the observation that all graphs are intersection graphs to Szpilrajn-Marczewski (1945), but say to see also Čulík (1964). The intersection number of a graph is the minimum total number of elements in any intersection representation of the graph.

Many important graph families can be described as intersection graphs of more restricted types of set families, for instance sets derived from some kind of geometric configuration:

Scheinerman (1985) characterized the intersection classes of graphs, families of finite graphs that can be described as the intersection graphs of sets drawn from a given family of sets. It is necessary and sufficient that the family have the following properties:

...
Wikipedia