On interval graphs and matrix profiles. (English) Zbl 0606.05063

Billionnet, Alain

RAIRO, Rech. Opér. 20, 245-256 (1986).

If an undirected graph is the intersection graph of a set of intervals of the real line, it is called an interval graph and the set of intervals is called an interval representation of the graph. In this paper, we recall a characterization of an interval graph given by Tarjan. This characterization allows us to show that the problem of minimizing the envelope size of a sparse symmetric matrix is NP-complete. Then we give a short proof of a known result about a Turan type problem for interval graphs. We prove also a new result on the decomposition of a graph in an intersection of interval graphs. The end of the paper is concerned by the chronological orderings of interval graphs. We give an 0(\(| E|)\) metod to determine whether an interval graph has a representation satisfying relative positions of the intervals.

MSC:

05C99

Graph theory

Keywords:

NP-completeness; matrix profile; optimization; interval graph; chronological orderings