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.
- A circular arc graph is defined as the intersection graph of arcs on a circle.
- A polygon-circle graph is defined as the intersection of polygons with corners on a circle.
- One characterization of a chordal graph is as the intersection graph of connected subgraphs of a tree.
- A trapezoid graph is defined as the intersection graph of trapezoids formed from two parallel lines. They are a generalization of the notion of permutation graph, in turn they are a special case of the family of the complements of comparability graphs known as cocomparability graphs.
- 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 (now a theorem) states that every planar graph can also be represented as an intersection graph of line segments in the plane. However, intersection graphs of line segments may be nonplanar as well, and recognizing intersection graphs of line segments is complete for the existential theory of the reals (Schaefer 2010).
- 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 curves 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.
Read more about this topic: Intersection Graph
Famous quotes containing the words classes of, classes and/or intersection:
“There were three classes of inhabitants who either frequent or inhabit the country which we had now entered: first, the loggers, who, for a part of the year, the winter and spring, are far the most numerous, but in the summer, except for a few explorers for timber, completely desert it; second, the few settlers I have named, the only permanent inhabitants, who live on the verge of it, and help raise supplies for the former; third, the hunters, mostly Indians, who range over it in their season.”
—Henry David Thoreau (1817–1862)
“I am ... by tradition and long study a complete snob. P. Marlowe and I do not despise the upper classes because they take baths and have money; we despise them because they are phony.”
—Raymond Chandler (1888–1959)
“If we are a metaphor of the universe, the human couple is the metaphor par excellence, the point of intersection of all forces and the seed of all forms. The couple is time recaptured, the return to the time before time.”
—Octavio Paz (b. 1914)