Split orders Original Research Article

In this paper, we study finite orders whose comparability graphs are split graphs. We introduce a normalized representation of these orders using a family of open real intervals. Its repercussions are both structural and algorithmic. We show that the dimension of split orders is at most three, and we give a simple characterization of those of dimension two. We present a linear time recognition algorithm for directed graphs whose transitive closures are split orders.