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

$\mathcal{P}_{1}$

and

$\mathcal{P}_{2}$

. In contrast, partial orders

P

which are the intersection of orders from the same class

$\mathcal{P}$

have been extensively investigated, and in most cases the complexity status of these recognition problems has been established.