Mertzios, 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. Berlin, Heidelberg: Springer, pp. 719-730. Lecture notes in computer science. (8125).
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.
|Item Type:||Book chapter|
|Keywords:||Intersection graphs, PI graphs, Recognition problem, Partial orders, Polynomial algorithm.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (347Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-40450-4_61|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-40450-4_61.|
|Date accepted:||No date available|
|Date deposited:||23 June 2015|
|Date of first online publication:||2013|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|