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.
Formally, an intersection graph is an undirected graph formed from a family of sets
:''S''_''i'', ''i'' = 0, 1, 2, ...
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,
:$E(G)=\{\{v\_i,v\_j\}mid\; S\_icap\; S\_j$
eemptyset}.
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. However, 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:

★ An interval graph is the intersection graph of intervals on the real line, or of connected subgraphs of a path.

★ A chordal graph is the intersection graph of connected subgraphs of a tree.

★ A unit disk graph is the intersection graph of unit disks in the plane.

★ The planar graphs are exactly the intersection graphs of families of closed disks in the plane bounded by non-crossing circles. Scheinerman's conjecture states that every planar graph can also be represented as an intersection graph of line segments in the plane.

★ The line graph of a graph ''G'' is the intersection graph of the edges of ''G'', where we represent each edge as the set of its two endpoints.

★ A graph has boxicity ''k'' if it is the intersection graph of ''k''-dimensional boxes.

Contents

References

References

★ Topics in Intersection Graph Theory, McKee, Terry A.; McMorris, F.R., , , Society for Industrial and Applied Mathematics (SIAM Monographs on Discrete Mathematics and Applications, No. 2), 1999, ISBN 0-89871-430-3