On the representation of . . .

Consider two parallel lines (denoted by r1 and r2). A graph is a PI graph (Point-Interval graph) if it is an intersection graph of a family F of triangles between r1 and r2such that each triangle has an interval with two endpoints on r1 and a vertex (a point)on r2. The family F is the PI representation of G. The PI graphs are an extension ofinterval 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 weshow how to construct a family of trapezoid graphs but not PI graphs from a trapezoid representation of a known graph in this class. Keywords: Algorithms, interval graphs, permutation graphs, trapezoid graphs, PI graphs