On the representation of a PI-Graph

Consider two parallel lines (denoted by $r_1$ and $r_2$). A graph is a PI graph (Point-Interval graph) if it is an intersection graph of a family F of triangles between $r_1$ and $r_2$ such that each triangle has an interval with two endpoints on $r_1$ and a vertex (a point) on $r_2$. The family F is the PI representation of G. The PI graphs are an extension of interval and permutation graphs and they form a subclass of trapezoid graphs. In this paper, we characterize the PI graphs in terms of its trapezoid representation. Also we show how to construct a family of trapezoid graphs but not PI graphs from a trapezoid representation of a known graph in this class.

2006