Recognition and characterization of chronological interval digraphs
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.
- Chronological orderings of interval digraphs
- A recognition algorithm for adjusted interval digraphs
- Chronological orderings of interval graphs
- scientific article; zbMATH DE number 4168705
- A characterization of interval catch digraphs
- Chronological rectangle digraphs
- Adjusted interval digraphs
- Recognizing interval digraphs and interval bigraphs in polynomial time
- A class of interval digraphs
- A Characterization of Comparability Graphs and of Interval Graphs
- A characterization of interval catch digraphs
- Adjusted interval digraphs
- An interval digraph in relation to its associated bipartite graph
- Chronological orderings of interval digraphs
- Chronological orderings of interval graphs
- Depth-First Search and Linear Graph Algorithms
- Homogeneously Representable Interval Bigraphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- In-tournament digraphs
- Incidence matrices and interval graphs
- Interval digraphs: An analogue of interval graphs
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- Interval Tournaments
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Representation characterizations of chordal bipartite graphs
- Representation of a finite graph by a set of intervals on the real line
- Representing digraphs using intervals or circular arcs
- Short proofs for interval digraphs
- Subpath acyclic digraphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The LBFS structure and recognition of interval graphs
- Algorithms for interval catch digraphs
- Chronological rectangle digraphs which are two-terminal series-parallel
- Chronological orderings of interval digraphs
- A recognition algorithm for adjusted interval digraphs
- Adjusted interval digraphs
- Miscellaneous digraph classes
- Chronological rectangle digraphs
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- On the kernel and related problems in interval digraphs
- Chronological orderings of interval graphs
This page was built for publication: Recognition and characterization of chronological interval digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396800)
