Publication details for Dr George MertziosMertzios, G.B. (2013). The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial. In Algorithms – ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings. Bodlaender, Hans L. & Italiano, Giuseppe F. Berlin, Heidelberg: Springer. 8125: 719-730.
- Publication type: Chapter in book
- ISSN/ISBN: 0302-9743 (print), 1611-3349 (electronic), 9783642404498 (print), 9783642404504 (electronic)
- DOI: 10.1007/978-3-642-40450-4_61
- Keywords: Intersection graphs, PI graphs, Recognition problem, Partial orders, Polynomial algorithm.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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 P1 and P2. 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.