Abstract |
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(n^1+a)$ recognition algorithm, where $O(n^a)$ is the time-complexity of the best known algorithm for matrix multiplication, actually $O(n^2,376)$ (Coppersmith and Winograd [1987 ). Has been revised into \citeReport-285-1991. |