Interval Digraphs

Abstract

We say that a simple, undirected graph interval graph if there exists a function mapping the vertices of the graph to intervals such that each pair of vertices is adjacent if and only if the corresponding intervals have a non-empty intersection. Undirected interval graphs were originally of interest for applications in biology, and the class of graphs has been thoroughly studied. In 1989, Das, Sen, Roy, and West introduced directed interval graphs or interval digraphs as a natural extension of the undirected interval graph. In this dissertation, we introduce a second type of interval digraphs and demonstrate that there exist separating examples for the two classes of graphs. We study properties of and present a recognition algorithm for the newly defined class, as well as comparing and contrasting the random properties of both models.