License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.591
URN: urn:nbn:de:0030-drops-30469
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3046/
Go to the corresponding LIPIcs Volume Portal

Mertzios, George B.

The Recognition of Triangle Graphs

pdf-format:
54.pdf (0.7 MB)

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.

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 =	{591--602},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3046},
  URN =		{urn:nbn:de:0030-drops-30469},
  doi =		{10.4230/LIPIcs.STACS.2011.591},
  annote =	{Keywords: Intersection graphs, trapezoid graphs, PI graphs, PI∗ graphs, recognition problem, NP-complete}
}

Keywords: Intersection graphs, trapezoid graphs, PI graphs, PI∗ graphs, recognition problem, NP-complete
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI