Recognition and characterization of chronological interval digraphs (Q396800)

Summary: Interval graphs admit elegant structural characterizations and linear time recognition algorithms; on the other hand, the usual interval digraphs lack a forbidden structure characterization as well as a low-degree polynomial time recognition algorithm. In this paper we identify another natural digraph analogue of interval graphs that we call ``chronological interval digraphs''. By contrast, the new class admits both a forbidden structure characterization and a linear time recognition algorithm. Chronological interval digraphs arise by interpreting the standard definition of an interval graph with a natural orientation of its edges. Specifically, \(G\) is a chronological interval digraph if there exists a family of closed intervals \(I_v\), \(v \in V(G)\), such that \(uv\) is an arc of \(G\) if and only if \(I_u\) intersects \(I_v\) and the left endpoint of \(I_u\) is not greater than the left endpoint of \(I_v\). (Equivalently, if and only if \(I_u\) contains the left endpoint of \(I_v\).) We characterize chronological interval digraphs in terms of vertex orderings, in terms of forbidden substructures, and in terms of a novel structure of so-called \(Q\)-paths. The first two characterizations exhibit strong similarity with the corresponding characterizations of interval graphs. The last characterization leads to a linear time recognition algorithm.