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, due to both 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 (point-interval) graphs---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. Given a graph $G$ with $n$ vertices, such that its complement $\overline{G}$ has $m$ edges, our algorithm runs in $O(n^{2}m)$ 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}\cap 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 complete contrast to this, 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 already established.

Citation

Mertzios, G. (2015). The recognition of simple-triangle graphs and of linear-interval orders is polynomial. SIAM Journal on Discrete Mathematics, 29(3), 1150-1185. https://doi.org/10.1137/140963108

• Journal Article Type: Article
• Acceptance Date: May 7, 2015
• Online Publication Date: Jul 16, 2015
• Publication Date: Jul 16, 2015
• Deposit Date: May 7, 2015
• Publicly Available Date: Jun 23, 2015
• Journal: SIAM Journal on Discrete Mathematics
• Print ISSN: 0895-4801
• Electronic ISSN: 1095-7146
• Publisher: Society for Industrial and Applied Mathematics
• Peer Reviewed: Peer Reviewed
• Volume: 29
• Issue: 3
• Pages: 1150-1185
• DOI: https://doi.org/10.1137/140963108
• Keywords: Intersection graph, PI graph, Recognition problem, Partial order, Polynomial algorithm.
• Public URL: https://durham-repository.worktribe.com/output/1406023