Intersection graph

From Wikipedia, the free encyclopedia

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 may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form an intersection representation of them.

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

Contents

[edit] Formal definition

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\varnothing\}.

[edit] All graphs are intersection graphs

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 more efficient construction in which the total number of set elements is at most n2/4. They credit the observation that all graphs are intersection graphs to Szpilrajn-Marczewski (1945), but say to see also Čulík (1963).

[edit] 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:

  • An interval graph is defined as the intersection graph of intervals on the real line, or of connected subgraphs of a path graph.
  • One characterization of a chordal graph is as the intersection graph of connected subgraphs of a tree.
  • A unit disk graph is defined as the intersection graph of unit disks in the plane.
  • The circle packing theorem states that 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 defined as the intersection graph of the edges of G, where we represent each edge as the set of its two endpoints.
  • A string graph is the intersection graph of strings on a plane.
  • A graph has boxicity k if it is the intersection graph of multidimensional boxes of dimension k, but not of any smaller dimension.

[edit] Related concepts

An order-theoretic analog to the intersection graphs are the containment 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 a containment 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) \subseteq f(y).

[edit] References

  • Čulík, K. (1963), “Applications of graph theory to mathematical logic and linguistics”, Proc. Symp. Graph Theory, Smolenice, pp. 13–20, MR0176940 .
  • Erdős, Paul; Goodman, A. W. & Pósa, Louis (1966), “The representation of a graph by set intersections”, Canadian Journal of Mathematics 18 (1): 106–112, MR0186575 .
  • 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), MR1672910, ISBN 0-89871-430-3 
  • Szpilrajn-Marczewski, E. (1945), “Sur deux propriétés des classes d'ensembles”, Fund. Math. 33: 303–307, MR0015448 .