The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders\n is Polynomial

Intersection graphs of geometric objects have been extensively studied, both\ndue to their interesting structure and their numerous applications; prominent\nexamples include interval graphs and permutation graphs. In this paper we study\na natural graph class that generalizes both interval and permutation graphs,\nnamely \\emph{simple-triangle} graphs. Simple-triangle graphs - also known as\n\\emph{PI} graphs (for Point-Interval) - are the intersection graphs of\ntriangles that are defined by a point on a line $L_{1}$ and an interval on a\nparallel line $L_{2}$. They lie naturally between permutation and trapezoid\ngraphs, which are the intersection graphs of line segments between $L_{1}$ and\n$L_{2}$ and of trapezoids between $L_{1}$ and $L_{2}$, respectively. Although\nvarious efficient recognition algorithms for permutation and trapezoid graphs\nare well known to exist, the recognition of simple-triangle graphs has remained\nan open problem since their introduction by Corneil and Kamula three decades\nago. In this paper we resolve this problem by proving that simple-triangle\ngraphs can be recognized in polynomial time. As a consequence, our algorithm\nalso solves a longstanding open problem in the area of partial orders, namely\nthe recognition of \\emph{linear-interval orders}, i.e. of partial orders\n$P=P_{1}\\cap P_{2}$, where $P_{1}$ is a linear order and $P_{2}$ is an interval\norder. This is one of the first results on recognizing partial orders $P$ that\nare the intersection of orders from two different classes $\\mathcal{P}_{1}$ and\n$\\mathcal{P}_{2}$. In complete contrast to this, partial orders $P$ which are\nthe intersection of orders from the same class $\\mathcal{P}$ have been\nextensively investigated, and in most cases the complexity status of these\nrecognition problems has been already established.\n