Interval graph
They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time.
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 vi for each interval Si, and connecting two vertices vi and vj 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 independent 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.
Many of the known algorithms for this problem work in this way, although it is also possible to recognize interval graphs in linear time without using their cliques.
[5] The original linear time recognition algorithm of Booth & Lueker (1976) is based on their complex PQ tree data structure, but Habib et al. (2000) showed how to solve the problem more simply using lexicographic breadth-first search, based on the fact that a graph is an interval graph if and only if it is chordal and its complement is a comparability graph.
[6] A similar approach using a 6-sweep LexBFS algorithm is described in Corneil, Olariu & Stewart (2009).
The trapezoid graphs, intersections of trapezoids whose parallel sides all lie on the same two parallel lines, are also a generalization of the interval graphs.
The connected triangle-free interval graphs are exactly the caterpillar trees.
[13] The mathematical theory of interval graphs was developed with a view towards applications by researchers at the RAND Corporation's mathematics department, which included young researchers—such as Peter C. Fishburn and students like Alan C. Tucker and Joel E. Cohen—besides leaders—such as Delbert Fulkerson and (recurring visitor) Victor Klee.
[14] Cohen applied interval graphs to mathematical models of population biology, specifically food webs.
[15] Interval graphs are used to represent resource allocation problems in operations research and scheduling theory.
In these applications, each interval represents a request for a resource (such as a processing unit of a distributed computing system or a room for a class) for a specific period of time.
The maximum weight independent set problem for the graph represents the problem of finding the best subset of requests that can be satisfied without conflicts.
An optimal graph coloring of the interval graph represents an assignment of resources that covers all of the requests with as few resources as possible; it can be found in polynomial time by a greedy coloring algorithm that colors the intervals in sorted order by their left endpoints.
[17] Other applications include genetics, bioinformatics, and computer science.
[18] Interval graphs also play an important role in temporal reasoning.
is an interval graph on the same vertex set that contains
The parameterized version of interval completion (find an interval supergraph with k additional edges) is fixed parameter tractable, and moreover, is solvable in parameterized subexponential time.
is the same as the smallest pathwidth of an interval graph that contains
[25] Because of this fast growth rate, the interval graphs do not have bounded twin-width.
