The Recognition of Triangle Graphs

George B. Mertzios
Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L_{1} and L_{2} of the plane. Strictly between permutation and trapezoid graphs lie the simple-triangle graphs -- also known as PI graphs (for Point-Interval) -- where the objects are triangles with one point of the triangle on L_1 and the other two points (i.e. interval) of the triangle on L_2, and the triangle...