Algorithmic study of 2-interval graphs
A.A.V. Simon (TU Delft - Electrical Engineering, Mathematics and Computer Science)
L.J.J. van Iersel – Mentor (TU Delft - Discrete Mathematics and Optimization)
M.M. de Weerdt – Graduation committee member (TU Delft - Algorithmics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.