A recognition algorithm for simple-triangle graphs

DOI10.1016/J.DAM.2019.11.009MaRDI QIDQ2185743zbMATH OpenOpenAlexFDO

Authors Asahi Takaoka

Publication date 5 June 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.06559

zbMATH Keywords

alternately orientable graphscocomparability graphsPI-graphsrecognition algorithmsimple-triangle graphsvertex-ordering characterization

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: A simple-triangle graph is the intersection graph of triangles that are defined by a point on a horizontal line and an interval on another horizontal line. The time complexity of the recognition problem for simple-triangle graphs was a longstanding open problem, which was recently settled. This paper provides a new recognition algorithm for simple-triangle graphs to improve the time bound from $O(n^{2}overlinem)$ to $O(nm)$, where $n$, $m$, and $overlinem$ are the number of vertices, edges, and non-edges of the graph, respectively. The algorithm uses the vertex ordering characterization that a graph is a simple-triangle graph if and only if there is a linear ordering of the vertices containing both an alternating orientation of the graph and a transitive orientation of the complement of the graph. We also show, as a byproduct, that an alternating orientation can be obtained in $O(nm)$ time for cocomparability graphs, and it is NP-complete to decide whether a graph has an orientation that is alternating and acyclic.

Recommendations

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

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A recognition algorithm for orders of interval dimension two
• A vertex ordering characterization of simple-triangle graphs
• Algorithmic graph theory and perfect graphs
• Alternating orientation and alternating colouration of perfect graphs
• Counterexamples to three conjectures concerning perfect graphs
• Efficient graph representations
• Fourth IFIP international conference on theoretical computer science -- TCS 2006. IFIP 19th world computer congress, TC-1, foundations of computer science, August 23--24, 2006, Santiago, Chile.
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3172312 (Why is no real title available?)
• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• Linear-Interval Dimension and PI Orders
• Modular decomposition and transitive orientation
• On the 2-Chain Subgraph Cover and Related Problems
• On the Ferrers dimension of a digraph
• On the Interplay Between Interval Dimension and Dimension
• On the structure of trapezoid graphs
• Proper and unit tolerance graphs
• The graph isomorphism problem on geometric graphs
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• The recognition of tolerance and bounded tolerance graphs
• The recognition of triangle graphs
• Tolerance graphs
• Tolerance graphs, and orders
• Topics in Intersection Graph Theory
• Transitiv orientierbare Graphen
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Trapezoid graphs and their coloring
• Vertex splitting and the recognition of trapezoid graphs

Cited in

(9)

• A vertex ordering characterization of simple-triangle graphs
• Algorithms and complexity of \(s\)-club cluster vertex deletion
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
• The recognition of triangle graphs
• Extended Learning Graphs for Triangle Finding
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• Computing shortest 12-representants of labeled graphs
• Graph classes equivalent to 12-representable graphs

This page was built for publication: A recognition algorithm for simple-triangle graphs

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