Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
The recognition of triangle graphs
Mertzios, G.B.
Authors
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.
Journal Article Type | Article |
---|---|
Publication Date | Jun 22, 2012 |
Deposit Date | Sep 5, 2014 |
Journal | Theoretical Computer Science |
Print ISSN | 0304-3975 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 438 |
Pages | 34-47 |
DOI | https://doi.org/10.1016/j.tcs.2012.02.042 |
Keywords | Intersection graphs, Trapezoid graphs, PI graphs, PI∗ graphs, Recognition problem, NP-complete. |
Public URL | https://durham-repository.worktribe.com/output/1445699 |
Related Public URLs | http://www.sciencedirect.com/science/article/pii/S0304397512001946 |
You might also like
The complexity of growing a graph
(2022)
Presentation / Conference Contribution
Payment scheduling in the Interval Debt Model
(2023)
Presentation / Conference Contribution
The complexity of computing optimum labelings for temporal connectivity
(2022)
Presentation / Conference Contribution
The complexity of temporal vertex cover in small-degree graphs
(2022)
Presentation / Conference Contribution
The complexity of transitively orienting temporal graphs
(2021)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search