Paper Info
Title
Recognition and Characterization of Chronological Interval Digraphs.
Abstract
Interval graphs admit elegant ordering and structural characterizations as well as linear time recognition algorithms. On the other hand, the usual interval digraphs lack all three of these characteristics. In this paper we identify another natural digraph analogue of interval graphs that we call "chronological interval digraphs". By contrast, the new class admits an ordering characterization, several forbidden substructure characterizations, as well as 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: G is a chronological interval digraph if there exists a family of closed intervals I-v; v is an element of V(G), such that uv is an arc of G if and only if I-u contains the left end point of I-v. We characterize chronological interval digraphs in terms of vertex orderings, and in terms of two kinds of forbidden substructures. These characterizations exhibit strong similarity with the corresponding characterizations of interval graphs, and lead to a linear time recognition algorithm.
Year
Venue
Field
2013
ELECTRONIC JOURNAL OF COMBINATORICS
Graph,Discrete mathematics,Combinatorics,Existential quantification,Vertex (geometry),Standard definition,If and only if,Recognition algorithm,Time complexity,Digraph,Mathematics
DocType
Volume
Issue
Journal
20.0
3.0
ISSN
Citations 
PageRank 
1077-8926
2
0.37
References 
Authors
7
4
Name
Order
Citations
PageRank
Sandip Das125648.78
Mathew C. Francis210714.90
Pavol Hell32638288.75
Jing Huang42464186.09