Bicoloured-interval and interval-sandwich graphs: two new classes in the tolerance hierarchy

Source abstract

We introduce two new graph classes, the bicoloured-interval graphs and the interval-sandwich graphs, arising from the study of the robust line fitting problem in computer vision. In a bicoloured-interval graph, each vertex is assigned a real interval and one of two colours. Vertices of different colours are adjacent precisely when their intervals intersect, and vertices of the same colour precisely when the centre of one interval lies in the other. Discarding the colouring yields the interval-sandwich graphs, sandwiched between the centre-containment graph and the intersection graph of a family of intervals. We prove structural results for both classes, determining which holes, antiholes, trees, and complete bipartite graphs each contains. Consequently, neither class is characterised by finitely many forbidden induced subgraphs. We place both classes strictly between the unit tolerance graphs and the co-comparability graphs in the tolerance hierarchy, separating them from the neighbouring classes. In particular, we construct an infinite family of proper tolerance graphs that are not bicoloured-interval graphs, each minimal with this property. Finally, we consider the recognition problem for both classes. We show that every graph in either class has a polynomial size integer representation, and hence that both problems lie in $\textsf{NP}$.