Intersection graph
In 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. Formal definition. Formally, an intersection graph "G" is an undirected graph formed from a family of sets by creating one vertex "v" for each set "S", and connecting two vertices "v" and "v" by an edge whenever the corresponding two sets have a nonempty  intersection, that is, All graphs are intersection graphs. Any undirected graph "G" may be represented as an intersection graph: for each vertex "v" of "G", form a set "S" consisting of the edges incident to "v"; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge. provide a construction that is more efficient (which is to say requires a smaller total number of elements in all of the sets "S" 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 , but say to see also . The intersection number of a graph is the minimum total number of elements in any intersection representation of the graph. Classes of intersection graphs. 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: 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. Related concepts. An order-theoretic analog  to the intersection graphs are the inclusion orders. In the same way that an intersection representation of a graph labels every vertex with a set so that vertices are adjacent if and only if their sets have nonempty intersection, so an inclusion representation "f" of a poset labels every element with a set so that for any "x" and "y" in the poset, "x" ≤ "y" if and only if "f"("x") ⊆ "f"("y").