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

Mertzios, G.B. (2012) 'The recognition of triangle graphs.', Theoretical computer science., 438 . pp. 34-47.

Abstract

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L1 and L2 of the plane. This subclass of perfect graphs has received considerable attention as it generalizes in a natural way both interval and permutation graphs. In particular, trapezoid graphs have been introduced in order to generalize some well known applications of these graphs on channel routing in integrated circuits. Strictly between permutation and trapezoid graphs lie the triangle graphs–also known as PI∗ graphs (for Point-Interval)–where the intersecting objects are triangles with one point of the triangle on the one line and the other two points (i.e. interval) of the triangle on the other line. Note that there is no restriction on which line between L1 and L2 contains one point of the triangle and which line contains the other two. Due to both their interesting structure and their practical applications, several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for trapezoid graphs–which also apply to triangle graphs. In spite of this, the complexity status of the triangle graph recognition problem (namely, the problem of deciding whether a given graph is a triangle graph) has been the most fundamental open problem on this class of graphs since its introduction two decades ago. Moreover, since triangle graphs lie naturally between permutation and trapezoid graphs, and since they share a very similar structure with them, it was expected that the recognition of triangle graphs is polynomial, as it is also the case for permutation and trapezoid graphs. In this article we surprisingly prove that the recognition of triangle graphs is NP-complete, even in the case where the input graph is known to be a trapezoid graph.

Item Type:Article
Keywords:Intersection graphs, Trapezoid graphs, PI graphs, PI∗ graphs, Recognition problem, NP-complete.
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1016/j.tcs.2012.02.042
Date accepted:No date available
Date deposited:No date available
Date of first online publication:June 2012
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar