Trapezoid graphs are a class of cocomparability graphs
containing interval graphs and permutation graphs as
subclasses. They were introduced by Dagan, Golumbic and
Pinter. They propose an O(n2) algorithm for
chromatic number and a less efficient algorithm for
maximum clique on trapezoid graphs. Based on a
geometric representation of trapezoid graphs by boxes
in the plane we design optimal, i.e., O(nlog n),
algorithms for chromatic number, weighted independent
set, clique cover and maximum weighted clique on such
graphs. We also propose generalizations of trapezoid
graphs called k-trapezoidal graphs. The ideas behind
the clique cover and weighted independent set
algorithms for trapezoid graphs carry over to higher
dimensions. This leads to O(nlogk-1n) algorithms
for k-trapezoidal graphs.
