Intersection graph

From Wikipedia, the free encyclopedia

You have new messages (last change).

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

Si, i = 0, 1, 2, ...

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,

E(G)=\{(v_i,v_j)\mid S_i\cap S_j\ne\emptyset\}.

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

[edit] References

  • McKee, Terry A.; McMorris, F.R. (1999). Topics in Intersection Graph Theory. Philadelphia: Society for Industrial and Applied Mathematics (SIAM Monographs on Discrete Mathematics and Applications, No. 2). ISBN 0-89871-430-3. 
Retrieved from "http://en.wikipedia.org../../../i/n/t/Intersection_graph.html"