Title: A recognition algorithm for simple-triangle graphs,
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 \overline{m})$ to $O(nm)$, where $n$, $m$, and
$\overline{m}$ 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.