Intersection graph

Formally, an intersection graph G is an undirected graph formed from a family of sets by creating one vertex vi for each set Si, and connecting two vertices vi and vj 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 vi of G, form a set Si consisting of the edges incident to vi; 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, in the sense that it requires a smaller total number of elements in all of the sets Si combined.

It is necessary and sufficient that the family have the following properties: If the intersection graph representations have the additional requirement that different vertices must be represented by different sets, then the clique expansion property can be omitted.

An order-theoretic analog to the intersection graphs are the inclusion orders.