DE graph

A DE graph (directed edge path graph) is the arc-intersection graph of a collection of directed paths of an oriented tree. Thus a graph [math]G[/math] is a DE graph if there is an oriented tree [math]T[/math], a collection [math]{\mathcal P}[/math] of directed paths of [math]T[/math], and a bijection [math]\pi: V(G) \to {\mathcal P}[/math] such that [math]uv \in E(G)[/math] if and only if [math]\pi(u)[/math] and [math]\pi(v)[/math] have a common arc.

DE graphs can be recognized in polynomial time, and a dipath-representation can also be computed . The class of DE graphs is a super-class of interval graphs and line graphs of bipartite graphs, and it is a subclass of perfect graphs.