Recognizing interval digraphs and interval bigraphs in polynomial time Original Research Article

An interval bigraph is an undirected bipartite graph whose edge set is the intersection of the edge sets of an interval graph and the edge set of a complete bipartite graph on the same vertex set. A bipartite interval representation of an interval bigraph is given by a bipartitioned set of intervals for its vertices, such that vertices are adjacent if and only if the corresponding intervals intersect and belong to opposite sides of the bipartition.