Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Interval graph
Summary
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line,
with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.
Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals.
These graphs have been used to model food webs, and to study scheduling problems in which one must select a subset of tasks to be performed at non-overlapping times. Other applications include assembling contiguous subsequences in DNA mapping, and temporal reasoning.
An interval graph is an undirected graph G formed from a family of intervals
by creating one vertex v_i for each interval 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, the edge set of G is
It is the intersection graph of the intervals.
Three vertices form an asteroidal triple (AT) in a graph if, for each two, there exists a path containing those two but no neighbor of the third. A graph is AT-free if it has no asteroidal triple. The earliest characterization of interval graphs seems to be the following:
A graph is an interval graph if and only if it is chordal and AT-free.
Other characterizations:
A graph is an interval graph if and only if its maximal cliques can be ordered such that each vertex that belongs to two of these cliques also belongs to all cliques between them in the ordering. That is, for every with , it is also the case that whenever .
A graph is an interval graph if and only if it does not contain the cycle graph as an induced subgraph and is the complement of a comparability graph.
Various other characterizations of interval graphs and variants have been described.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.