📜 ⬆️ ⬇️

Intersection graph

Intersection graph.gif

In graph theory, an intersection graph is a graph intersection scheme of a family of sets . Any graph can be represented as an intersection graph, but some important special classes can be defined by the types of sets used to represent as intersections of sets.

For a review of intersection graph theory and important special classes of intersection graphs, see McKee and McMorris ^[1] .

Formal Definition

The intersection graph is an undirected graph formed from a family of sets

S_{i},i=0,1,2,...

{\ displaystyle S_ {i}, i = 0,1,2, ...}

S_{i},i=0,1,2,...

by creating the top $v_{i}$ ${\ displaystyle v_ {i}}$ $v_{i}$ for each set $S_{i}$ ${\ displaystyle S_ {i}}$ $S_{i}$ and joining two vertices $v_{i}$ ${\ displaystyle v_ {i}}$ $v_{i}$ and $v_{j}$ ${\ displaystyle v_ {j}}$ $v_{j}$ edge if the corresponding two sets have a nonempty intersection, i.e.

E(G)=\{\{v_{i},v_{j}\}|S_{i}\cap S_{j}\neq \emptyset \}

{\ displaystyle E (G) = \ {\ {v_ {i}, v_ {j} \} | S_ {i} \ cap S_ {j} \ neq \ emptyset \}}

E(G)=\{\{v_{i},v_{j}\}|S_{i}\cap S_{j}\neq \emptyset \}

.

All graphs are intersection graphs.

Any undirected graph G can be represented as an intersection graph - for any vertex $v_{i}$ ${\ displaystyle v_ {i}}$ $v_{i}$ of the graph G we form the set $S_{i}$ ${\ displaystyle S_ {i}}$ $S_{i}$ consisting of ribs incident $v_{i}$ ${\ displaystyle v_ {i}}$ $v_{i}$ . Two such sets have a nonempty intersection if and only if the corresponding vertices belong to one edge. Erdös, Goodman, and Pose ^[2] showed a more efficient construction (which requires fewer elements in all sets $S_{i}$ ${\ displaystyle S_ {i}}$ $S_{i}$ ), in which the total number of elements in the sets does not exceed $n^{2}/4$ ${\ displaystyle n ^ {2} / 4}$ $n^{2}/4$ where n is the number of vertices in the graph. According to them, all graphs are intersection graphs, noted Marchevsky ^[3] , but also recommended looking at Chulik's work ^[4] . The number of intersections of a graph is the minimum number of elements in the representations of the graph as the intersection graph.

Intersection Graph Classes

Many important families of graphs can be described as intersection graphs of bounded types of sets, for example, sets obtained from some geometric configurations:

An interval graph is defined as a graph of intersections of intervals on a straight line, or connected path subgraphs.
The graph of circular arcs is defined as the intersection graph of circular arcs .
The graph of polygons on a circle is defined as the graph of intersections of polygons with vertices lying on a circle.
One of the characteristics of chordal graphs is that they are intersection graphs of connected subgraphs of a tree .
A trapezoidal graph is defined as the intersection graph of trapezoids formed by two parallel lines. They are a generalization of the concept of a permutation graph , which, in turn, is a special case of a family of complements of comparability graphs known as co- comparability graphs.
The graph of unit circles is defined as the graph of intersections of unit circles on the plane.
The circle packing theorem states that planar graphs are exactly the intersection graphs of families of closed disjoint (allowed to touch) disks on the plane.
now (now a theorem) states that any planar graph can be represented as a graph of intersections of segments on a plane. However, the intersection graphs of line segments can be unplanar, and recognition of the intersection graphs of line segments is for the ^[5] .
The edge graph of the graph G is defined as the intersection graph of the edges of the graph G , where each edge is considered as the set of its two end vertices.
A string graph is a graph of intersections of curves on a plane .
A graph has frame k if it is the intersection graph of multidimensional rectangles of dimension k , but not smaller than dimensions.

Variations and generalizations

Theoretical analogues of the order of intersection graphs are . In exactly the same way as the representation of the intersection graph marks each vertex with the set of edges incident to it that have a nonempty intersection, the representation of the nesting order f of the partially ordered set marks each element with such a set that for any x and y in it $x\leq y$ ${\ displaystyle x \ leq y}$ if and only if $f(x)\subseteq f(y)$ ${\ displaystyle f (x) \ subseteq f (y)}$ .
Nerve cover

Notes

↑ McKee, McMorris, 1999 .
↑ Erdős, Goodman, Pósa, 1966 .
↑ Szpilrajn-Marczewski, 1945 .
↑ Čulík, 1964 .
↑ Schaefer, 2010 .

Literature

K. Čulík. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). - Prague: Publ. House Czechoslovak Acad. Sci., 1964. - S. 13-20.
Paul Erdős, AW Goodman, Louis Pósa. The representation of a graph by set intersections // Canadian Journal of Mathematics. - 1966. - T. 18 . - S. 106-112 . - DOI : 10.4153 / CJM-1966-014-3 .
Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. - Academic Press, 1980. - ISBN 0-12-289260-7 .
Topics in Intersection Graph Theory. - Philadelphia: Society for Industrial and Applied Mathematics, 1999. - T. 2. - (SIAM Monographs on Discrete Mathematics and Applications). - ISBN 0-89871-430-3 .
E. Szpilrajn-Marczewski. Sur deux propriétés des classes d'ensembles // Fund. Math. . - 1945 .-- T. 33 . - S. 303-307 .
Marcus Schaefer. Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers . - Springer-Verlag, 2010 .-- Vol. 5849. - S. 334—344. - (Lecture Notes in Computer Science). - ISBN 978-3-642-11804-3 . - DOI : 10.1007 / 978-3-642-11805-0_32 .

Links

Jan Kratochvíl, A video lecture on intersection graphs (June 2007)
E. Prisner, A Journey through Intersection Graph County

Source - https://ru.wikipedia.org/w/index.php?title= Intersection graph&oldid = 91623835

All articles