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

Mertzios, G.B.

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 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.

Citation

Mertzios, G. (2013). The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial. In H. L. Bodlaender, & G. F. Italiano (Eds.), Algorithms - ESA 2013 : 21st annual European symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings (719-730). Springer Verlag. https://doi.org/10.1007/978-3-642-40450-4_61

• Publication Date: Sep 4, 2013
• Deposit Date: Sep 5, 2014
• Publicly Available Date: Jun 23, 2015
• Publisher: Springer Verlag
• Pages: 719-730
• Series Title: Lecture notes in computer science
• Book Title: Algorithms - ESA 2013 : 21st annual European symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings.
• ISBN: 9783642404498
• DOI: https://doi.org/10.1007/978-3-642-40450-4_61
• Keywords: Intersection graphs, PI graphs, Recognition problem, Partial orders, Polynomial algorithm.
• Public URL: https://durham-repository.worktribe.com/output/1677845