Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

The recognition of simple-triangle graphs and of linear-interval orders is polynomial.

Mertzios, G.B. (2015) 'The recognition of simple-triangle graphs and of linear-interval orders is polynomial.', SIAM journal on discrete mathematics., 29 (3). pp. 1150-1185.

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.

Item Type:Article
Keywords:Intersection graph, PI graph, Recognition problem, Partial order, Polynomial algorithm.
Full text:(AM) Accepted Manuscript
Download PDF
(491Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1137/140963108
Publisher statement:Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
Date accepted:07 May 2015
Date deposited:23 June 2015
Date of first online publication:16 July 2015
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar