Trapezoid Graphs and Generalizations, Geometry and Algorithms
Stefan Felsner, Rudolf Müller, Lorenz Wernisch
Institut für Informatik
Freie Universität Berlin
email: felsner@inf.fu-berlin.de
Report B 94-02
January 94
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-02.ps.gz
Trapezoid graphs are a class of cocomparability graphs and permutation graphs as subclasses. They were introduced by Dagan, Golumbic and Pinter [DGP]. 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 reporsentation of trapezoid graphs by boxes in the plane we design optimal, i.e., $O(n\log 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(n\log^{k-1}n)$ algorithms for $k$-trapezoidal graphs. We also propose a new class of graphs called {\it circle trapezoid graphs\/}. This class contains trapezoid graphs, circle graphs and circular-arc graphs as subclasses. We show that clique and independent set problems for circle trapezoid graphs are still polynomially solvable. The algorithms solving these two problems require algorithms for trapezoid graphs as subroutines.