Interval Digraphs
Embargo until
Date
2019-02-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Johns Hopkins University
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.
Description
Keywords
graph theory, interval graphs, interval digraphs, random graphs