A characterization of interval orders with semiorder dimension two

Given a partial order Q, its semiorder dimension is the smallest number of semiorders whose intersection is Q. When we look at the class of partial orders of fixed semiorder dimension k, no characterization is known, even in the case k = 2. In this paper, we give a characterization of the class of interval orders with semiorder dimension two. It follows from our results that partial orders that are interval orders with semiorder dimension two can be recognized efficiently. As our characterization makes use of a certain substructure, we also discuss the possibility of a forbidden suborder characterization. We give a partial answer to this question by listing all forbidden suborders for a special case. We further transfer our characterization result to the class of interval graphs that induce orders with semiorder dimension two. (C) 2021 Published by Elsevier B.V.