The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial

DOI10.1007/978-3-642-40450-4_61MaRDI QIDQ2849360zbMATH OpenOpenAlexFDO

Authors George B. Mertzios

Publication date 17 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.4352, http://dro.dur.ac.uk/13472/1/13472.pdf

zbMATH Keywords

intersection graphspartial ordersrecognition problempolynomial algorithmPI graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Partial orders, general (06A06) Analysis of algorithms and problem complexity (68Q25) Graph representations (geometric and intersection representations, etc.) (05C62)

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 emph{simple-triangle} graphs. Simple-triangle graphs - also known as emph{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 emph{linear-interval orders}, i.e. of partial orders $P=P_{1}cap{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 $mathcal{P}_1$ and $mathcal{P}_2$. In complete contrast to this, partial orders $P$ which are the intersection of orders from the same class $mathcalP$ have been extensively investigated, and in most cases the complexity status of these recognition problems has been already established.

Recommendations

• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• A vertex ordering characterization of simple-triangle graphs
• A recognition algorithm for simple-triangle graphs
• The interval order polytope of a digraph
• Polygonal graphs as ordered sets: the Sperner criterion
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Linear recognition of almost interval graphs
• The recognition of triangle graphs
• The recognition of triangle graphs
• Recognition of some perfectly orderable graph classes

Cited in

(5)

• A vertex ordering characterization of simple-triangle graphs
• The recognition of triangle graphs
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• Linear-Interval Dimension and PI Orders
• A recognition algorithm for simple-triangle graphs

This page was built for publication: The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849360)