The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial

摘要

Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph class that generalizes both interval and permutation graphs, namely simple-triangle graphs. Simple-triangle graphs - also known as PI graphs (for Point-Interval) - are the intersection graphs of triangles that are defined by a point on a line L_1 and an interval on a parallel line L_2. They lie naturally between permutation and trapezoid graphs, which are the intersection graphs of line segments between L_1 and L_2 and of trapezoids between L_1 and L_2, respectively. Although various efficient recognition algorithms for permutation and trapezoid graphs are well known to exist, the recognition of simple-triangle graphs has remained an open problem since their introduction by Corneil and Kamula three decades ago. In this paper we resolve this problem by proving that simple-triangle graphs can be recognized in polynomial time. As a consequence, our algorithm also solves a longstanding open problem in the area of partial orders, namely the recognition of linear-interval orders, i.e. of partial orders P = P_1 ∩ P_2, where P_1 is a linear order and P_2 is an interval order. This is one of the first results on recognizing partial orders P that are the intersection of orders from two different classes P_1 and P_2. In contrast, partial orders P which are the intersection of orders from the same class P have been extensively investigated, and in most cases the complexity status of these recognition problems has been established.