Print Email Facebook Twitter Algorithmic study of 2-interval graphs Title Algorithmic study of 2-interval graphs Author Simon, Alexandre (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor van Iersel, L.J.J. (mentor) de Weerdt, M.M. (graduation committee) Degree granting institution Delft University of Technology Date 2021-08-18 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. Subject Graph theoryAlgorithmsInterval graphsd-track graphst-interval graphsNP-hard problems To reference this document use: http://resolver.tudelft.nl/uuid:e899eff1-bd18-4007-bfbb-b57cdd893a81 Part of collection Student theses Document type master thesis Rights © 2021 Alexandre Simon Files PDF Thesis_3_.pdf 579.32 KB Close viewer /islandora/object/uuid:e899eff1-bd18-4007-bfbb-b57cdd893a81/datastream/OBJ/view