TRAPEZOID GRAPHS AND GENERALIZATIONS, GEOMETRY AND ALGORITHMS

Trapezoid graphs are a class of cocomparability graphs containing inte rval graphs and permutation graphs as subclasses. They were introduced by Dagan et al. [3]. They propose an O(n(2)) algorithm for chromatic number and a less efficient algorithm for maximum clique on trapezoid graphs. Based on a geometric representation of trapezoid graphs by box es in the plane we design optimal, i.e., O(n log n), algorithms for ch romatic number, weighted independent set, clique cover and maximum wei ghted clique on such graphs. We also propose generalizations of trapez oid graphs called k-trapezoid graphs. The ideas behind the clique cove r and weighted independent set algorithms for trapezoid graphs carry o ver to higher dimensions. This leads to O(n log(k-1) n) algorithms for k-trapezoid graphs. We also propose a new class of graphs called circ le trapezoid graphs. This class contains trapezoid graphs, circle grap hs and circular-arc graphs as subclasses. We show that clique and inde pendent set problems for circle trapezoid graphs are efficiently solva ble. The algorithms solving these two problems require algorithms for trapezoid graphs as subroutines.