This paper is devoted to the study of structural
properties needed for the construction of a fast
algorithm to recognize trapezoid graphs. These graphs
constitute a class of perfect graphs that naturally
arise in VLSI channel routing problems. In section I,
we present how a result of Cogis about Ferrers
dimension and a comparability invariance theorem of
Habib, Kelly and Möhring can solve some questions
asked by Dagan, Golumbic and Pinter [1988 about the
complexity of recognizing trapezoid graphs and an open
problem of Yannakakis [1982 about the complexity of
recognizing partial orders having interval dimension
two. In fact this notion of comparability invariance
allows to consider equivalently trapezoid graphs and
trapezoid orders, i.e. transitive orientations of the
complement of a trapezoid graph which are exactly the
partial orders of interval dimension two. In section
II, we describe a sequence of transformations of the
original problem, guided by our algorithmic search and
produce some characterizations of trapezoid orders. We
finish in section III by generalizing for this class of
partial orders some results of Golumbic [1980 about
transitive orientations of comparability graphs. These
results yield an O(n1+a) recognition algorithm,
where O(na) is the time-complexity of the best known
algorithm for matrix multiplication, actually
O(n2,376) (Coppersmith and Winograd [1987 ). Has
been revised into Report-285-1991}.
