Algorithmic study of 2-interval graphs

Abstract

Interval graphs play an important role in graph theory and have intensively been studied for over sixty years due to their wide range of applications and because most NP-hard problems on general graphs become solvable in linear time on interval graphs. However, the class of interval graphs is restricted and does not even contain a cycle of length 4. To overcome this drawback, we study some generalisations of interval graphs where instead of considering one interval on one real line for each vertex we consider d intervals on d different real lines and take the union of each lines (d-track graphs) or t intervals on the same real line (t-interval graphs). Nevertheless, most problems now become NP-hard as shown for Vertex Cover, Clique Cover, Biclique Cover or even APX-hard in the case of Feedback Vertex Set. This is even the case if we add some restrictions on the length of the intervals. We also give a bound on the unit track number of any interval graph (number of tracks needed so that all the intervals have the same length). Furthermore, we study the relationship between the classes of d-track graphs and t-interval graphs with the length of the intervals restricted or not. Finally, we also consider taking the intersection of d tracks (boxicity d graphs) and show that is it not more or less restrictive than taking the union of d tracks.