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

DOI10.1007/978-3-642-40450-4_61zbMATH Open1394.68190arXiv1210.4352OpenAlexW2963089667MaRDI QIDQ2849360FDOQ2849360

Publication date: 17 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: 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 emph{simple-triangle} graphs. Simple-triangle graphs - also known as emph{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 emph{linear-interval orders}, i.e. of partial orders