2-interval graphs (research training at LIAFA with Michel Habib)

(En français)

2-interval graphs

2-interval graphs can represent a collection of pairs of intervals on the real line : vertices are the 2-intervals, and they are linked by an edge if the 2-intervals have a non-empty intersection. Many problems can be studied using those graphs: the secondary structure of RNA, or the scheduling of tasks split in two parts, like those linked with radars.

A graph-theoretical approach to these problems makes it possible to use the abundant literature on the subject. Indeed, we try to transform the problem, or some variation to get a better complexity, into a problem (mostly Maximum Independent Set) on a graph of some class, well known... or to be explored to discover its properties and locate it in the graph classes hierarchy.

Documents:

• On restrictions of balanced 2-interval graphs, an article with Stéphane Vialette presented at WG'07 (PDF slides, OpenOffice source, sound).
• A BibTex about 2-interval graphs.
• A nicer version of the ISGCI page about 2-interval graphs (also for claw-free and a new page for quasi-line graphs).
• Master's Thesis in French: Les graphes 2-intervallaires.

Back to the main page