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 harvtxt|McKee|McMorris|1999.
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,:
All graphs are intersection graphs
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. harvtxt|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 harvtxt|Szpilrajn-Marczewski|1945, but say to see also harvtxt|Čulík|1963.
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:
interval graphis defined as the intersection graph of intervals on the real line, or of connected subgraphs of a path graph.
circular arc graphis defined as the intersection graph of arcs on a circle.
* One characterization of a
chordal graphis as the intersection graph of connected subgraphs of a tree.
unit disk graphis defined as the intersection graph of unit disks in the plane.
circle packing theoremstates that planar graphs are exactly the intersection graphs of families of closed disks in the plane bounded by non-crossing circles. Scheinerman's conjecturestates that every planar graph can also be represented as an intersection graph of line segments in the plane.
line graphof 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.
string graphis 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.
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 posetlabels 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").
last = Čulík | first = K.
contribution = Applications of graph theory to mathematical logic and linguistics
title = Proc. Symp. Graph Theory, Smolenice
year = 1963 | pages = 13–20 | id = MathSciNet | id=0176940.
last1 = Erdős | first1 = Paul | authorlink1 = Paul Erdős
last2 = Goodman | first2 = A. W. | last3 = Pósa | first3 = Louis
title = The representation of a graph by set intersections
journal = Canadian Journal of Mathematics
volume = 18 | issue = 1 | year = 1966 | pages = 106–112
id = MathSciNet | id=0186575.
last1 = McKee | first1 = Terry A. | last2 = McMorris | first2 = F. R.
title = Topics in Intersection Graph Theory
year = 1999
publisher = Society for Industrial and Applied Mathematics (SIAM Monographs on Discrete Mathematics and Applications, No. 2)
location = Philadelphia
isbn = 0-89871-430-3 | id = MathSciNet | id = 1672910
first = E. | last = Szpilrajn-Marczewski
title = Sur deux propriétés des classes d'ensembles
journal = Fund. Math. | volume = 33 | year = 1945 | pages = 303–307
id = MathSciNet | id = 0015448.
Wikimedia Foundation. 2010.
Look at other dictionaries:
Intersection number (graph theory) — In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of G as an intersection graph of finite sets. Equivalently, it is the smallest number of cliques needed to cover… … Wikipedia
Intersection (set theory) — Intersections of the Greek, Latin and Russian alphabet (upper case graphemes) (The intersection of Greek and Latin letters is used for the Greek licence plates.) … Wikipedia
Graph drawing — This article is about the general subject of graph drawing. For the annual research symposium, see International Symposium on Graph Drawing. Graphic representation of a minute fraction of the WWW, demonstrating hyperlinks. Graph drawing is an… … Wikipedia
graph — /graf, grahf/, n. 1. a diagram representing a system of connections or interrelations among two or more things by a number of distinctive dots, lines, bars, etc. 2. Math. a. a series of points, discrete or continuous, as in forming a curve or… … Universalium
Intersection array — In graph theory, given a distance regular graph G of diameter d , by definition there are integers b i and c i such that given any two vertices x and y in G at distance i , y has b i neighbours at distace i +1 from x and c i neighbours at… … Wikipedia
Chordal graph — A cycle (black) with two chords (green). As for this part, the graph is chordal. However, removing one green edge would result in a non chordal graph. Indeed, the other green edge with three black edges would form a cycle of length four with no… … Wikipedia
Circle graph — For the chart, see Pie chart. A circle with five chords and the corresponding circle graph. In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be… … Wikipedia
Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… … Wikipedia
Distance-hereditary graph — A distance hereditary graph. In graph theoretic mathematics, a distance hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original… … Wikipedia
Line graph of a hypergraph — The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph, with two edges adjacent when they have nonempty intersection. In other words, the line graph of a hypergraph is the intersection graph of … Wikipedia