Mertzios, G.B. (2011) 'The recognition of triangle graphs.', in *28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, 10-12 March 2011, Dortmund, Germany ; proceedings.* Dagstuhl, Germany: Schloss Dagstuhl, pp. 591-602. Leibniz International Proceedings in Informatics (LIPIcs). (9).

## Abstract

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L_{1} and L_{2} of the plane. Strictly between permutation and trapezoid graphs lie the simple-triangle graphs -- also known as PI graphs (for Point-Interval) -- where the objects are triangles with one point of the triangle on L_1 and the other two points (i.e. interval) of the triangle on L_2, and the triangle graphs -- also known as PI^* graphs -- where again the objects are triangles, but now there is no restriction on which line contains one point of the triangle and which line contains the other two. The complexity status of both triangle and simple-triangle recognition problems (namely, the problems of deciding whether a given graph is a triangle or a simple-triangle graph, respectively) have been the most fundamental open problems on these classes of graphs since their introduction two decades ago. Moreover, since triangle and simple-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 and simple-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: | Book chapter |
---|---|

Keywords: | Intersection graphs, Trapezoid graphs, PI graphs, PI∗, Graphs, Recognition problem, NP-complete. |

Full text: | PDF - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. (742Kb) |

Status: | Peer-reviewed |

Publisher Web site: | http://dx.doi.org/10.4230/LIPIcs.STACS.2011.591 |

Publisher statement: | This paper is made available under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License. The CC by-nc-nd license allows you to copy, distribute and transmit the work under the following conditions: Attribution: You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work). Noncommercial: You may not use this work for commercial purposes. No Derivative Works: You may not alter, transform, or build upon this work. |

Record Created: | 10 Jan 2012 10:20 |

Last Modified: | 17 Jan 2012 14:20 |

Social bookmarking: | Export: EndNote, Zotero | BibTex |

Usage statistics | Look up in GoogleScholar | Find in a UK Library |