Mertzios, George B.
The Recognition of Triangle Graphs
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 simpletriangle graphs  also known as PI graphs (for PointInterval)  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 simpletriangle recognition problems (namely, the problems of deciding whether a given graph is a triangle or a simpletriangle graph, respectively) have been the most fundamental open problems on these classes of graphs since their introduction two decades ago. Moreover, since triangle and simpletriangle 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 simpletriangle 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 NPcomplete, even in the case where the input graph is known to be a trapezoid graph.
BibTeX  Entry
@InProceedings{mertzios:LIPIcs:2011:3046,
author = {George B. Mertzios},
title = {{The Recognition of Triangle Graphs}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {591602},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3046},
URN = {urn:nbn:de:0030drops30469},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.591},
annote = {Keywords: Intersection graphs, trapezoid graphs, PI graphs, PI∗ graphs, recognition problem, NPcomplete}
}
Keywords: 

Intersection graphs, trapezoid graphs, PI graphs, PI∗ graphs, recognition problem, NPcomplete 
Seminar: 

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Issue date: 

2011 
Date of publication: 

11.03.2011 