Summary: A \(d\)-interval is the union of \(d\) disjoint intervals on the real line. A \(d\)-track interval is the union of \(d\) disjoint intervals on \(d\) disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, \(d\)-interval graphs and \(d\)-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing \(d\)-track interval graphs is NP-complete for any constant \(d\geq 2\). This confirms a conjecture of Gyárfás and West from 1995. Previously only the complexity of the case \(d=2\) was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced \(d\)-track interval graphs, unit \(d\)-track interval graphs, and \((2,\dots ,2)\) \(d\)-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit \(d\)-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys from 1984 and a similar question of Gyárfás and West from 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity.