Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
Mertzios, G.B.
Authors
Contributors
Hans L. Bodlaender
Editor
Giuseppe F. Italiano
Editor
Abstract
Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph class that generalizes both interval and permutation graphs, namely simple-triangle graphs. Simple-triangle graphs – also known as PI graphs (for Point-Interval) – are the intersection graphs of triangles that are defined by a point on a line L 1 and an interval on a parallel line L 2. They lie naturally between permutation and trapezoid graphs, which are the intersection graphs of line segments between L 1 and L 2 and of trapezoids between L 1 and L 2, respectively. Although various efficient recognition algorithms for permutation and trapezoid graphs are well known to exist, the recognition of simple-triangle graphs has remained an open problem since their introduction by Corneil and Kamula three decades ago. In this paper we resolve this problem by proving that simple-triangle graphs can be recognized in polynomial time. As a consequence, our algorithm also solves a longstanding open problem in the area of partial orders, namely the recognition of linear-interval orders, i.e. of partial orders P = P 1 ∩ P 2, where P 1 is a linear order and P 2 is an interval order. This is one of the first results on recognizing partial orders P that are the intersection of orders from two different classes P1 and P2. In contrast, partial orders P which are the intersection of orders from the same class P have been extensively investigated, and in most cases the complexity status of these recognition problems has been established.
Publication Date | Sep 4, 2013 |
---|---|
Deposit Date | Sep 5, 2014 |
Publicly Available Date | Jun 23, 2015 |
Publisher | Springer Verlag |
Pages | 719-730 |
Series Title | Lecture notes in computer science |
Book Title | Algorithms - ESA 2013 : 21st annual European symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings. |
ISBN | 9783642404498 |
DOI | https://doi.org/10.1007/978-3-642-40450-4_61 |
Keywords | Intersection graphs, PI graphs, Recognition problem, Partial orders, Polynomial algorithm. |
Public URL | https://durham-repository.worktribe.com/output/1677845 |
Files
Accepted Book Chapter
(355 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-40450-4_61.
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