The recognition of triangle graphs

Abstract

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L1 and L2 of the plane. This subclass of perfect graphs has received considerable attention as it generalizes in a natural way both interval and permutation graphs. In particular, trapezoid graphs have been introduced in order to generalize some well known applications of these graphs on channel routing in integrated circuits. Strictly between permutation and trapezoid graphs lie the triangle graphs–also known as PI∗ graphs (for Point-Interval)–where the intersecting objects are triangles with one point of the triangle on the one line and the other two points (i.e. interval) of the triangle on the other line. Note that there is no restriction on which line between L1 and L2 contains one point of the triangle and which line contains the other two. Due to both their interesting structure and their practical applications, several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for trapezoid graphs–which also apply to triangle graphs. In spite of this, the complexity status of the triangle graph recognition problem (namely, the problem of deciding whether a given graph is a triangle graph) has been the most fundamental open problem on this class of graphs since its introduction two decades ago. Moreover, since triangle graphs lie naturally between permutation and trapezoid graphs, and since they share a very similar structure with them, it was expected that the recognition of triangle graphs is polynomial, as it is also the case for permutation and trapezoid graphs. In this article we surprisingly prove that the recognition of triangle graphs is NP-complete, even in the case where the input graph is known to be a trapezoid graph.