Interval digraphs: An analogue of interval graphs

TLDR

Intersection digraphs are defined by assigning each vertex an ordered pair of sets, with a directed edge from u to v when u’s source set intersects v’s terminal set; interval digraphs are the subclass where all sets are real‑line intervals, though not every digraph admits such a convex representation. The paper introduces intersection digraphs as directed analogues of undirected intersection graphs. Interval digraphs are characterized by the consecutive‑ones property of certain matrices, by their adjacency matrices, and by their representation as intersections of Ferrers digraphs. They are precisely the intersections of pairs of Ferrers digraphs whose union forms a complete digraph.

Abstract

Abstract Intersection digraphs analogous to undirected intersection graphs are introduced. Each vertex is assigned an ordered pair of sets, with a directed edge uv in the intersection digraph when the “source set” of u intersects the “terminal set” of v. Every n ‐vertex digraph is an intersection digraph of ordered pairs of subsets of an n ‐set, but not every digraph is an intersection digraph of convex sets in the plane. Interval digraphs are those having representations where all sets are intervals on the real line. Interval digraphs are characterized in terms of the consecutive ones property of certain matrices, in terms of the adjacency matrix and in terms of Ferrers digraphs. In particular, they are intersections of pairs of Ferrers digraphs whose union is a complete digraph.