Recognition and characterization of chronological interval digraphs (Q396800)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Recognition and characterization of chronological interval digraphs
scientific article

    Statements

    Recognition and characterization of chronological interval digraphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    14 August 2014
    0 references
    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.
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references