×

Trapezoid graphs and their coloring. (English) Zbl 0658.05067

The authors’ abstract: “We define trapezoid graphs, an extension of both interval and permutation graphs. We show that this new class properly contains the union of the two classes, and that trapezoid graphs are equivalent to the incomparability graphs of partially ordered sets having interval order dimension at most two. We provide an optimal coloring algorithm for trapezoid graphs that runs in time O(nk), where n is the number of nodes and k is the chromatic number of the graph. Our coloring algorithm has direct applications to channel routing on integrated circuits.”
Reviewer: R.L.Hemminger

MSC:

05C99 Graph theory
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burstein, M., Channel routing, (Ohtsuki, T., Layout Design and Verification (1986), North-Holland: North-Holland Amsterdam), 132-167
[2] Corneil, D. G.; Kamula, P. A., Extensions of permutation and interval graphs, Proceedings 18th Southeastern Conference on Combinatorics, Graph Theory and Computing (1987) · Zbl 0652.05055
[3] Even, S.; Pnueli, A.; Lempel, A., Permutation graphs and transitive graphs, J. Assoc. Comput. Mach., 19, 400-410 (1972) · Zbl 0251.05113
[4] Fishburn, P. C., Interval Orders and Interval Graphs (1985), Wiley: Wiley New York · Zbl 0216.30401
[5] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[6] Golumbic, M. C., Algorithmic aspects of intersection graphs and representation hypergraphs, Proceedings First International Japan Conference on Graph Theory and Applications (1986), also: Graphs and Combinatorics (to appear)
[7] Golumbic, M. C.; Monma, C. L.; Trotter, W. T., Tolerance graphs, Discrete Appl. Math., 9, 157-170 (1984) · Zbl 0547.05054
[8] Golumbic, M. C.; Rotem, D.; Urrutia, J., Comparability graphs and intersection graphs, Discrete Math., 43, 37-46 (1983) · Zbl 0502.05050
[9] Hoffman, A. J., On greedy algorithms that succeed, (Anderson, I., Surveys in Combinatorics 1985 (1985), Cambridge University Press: Cambridge University Press Cambridge, England), 97-112 · Zbl 0601.90111
[10] Johnson, D. S., The NP-completeness column: An ongoing guide, J. Algorithms, 6, 434-451 (1985) · Zbl 0608.68032
[11] Leiserson, C. E.; Pinter, R. Y., Optimal placement for river routing, SIAM J Comput., 12, 447-462 (1983) · Zbl 0512.94029
[12] Pinter, R. Y., The impact of layer assignment methods on layout algorithms for integrated circuits, (Ph.D. Thesis (1982), MIT: MIT Cambridge, MA)
[13] Pinter, R. Y., River routing: Methodology and analysis, Proceedings Third Caltech Conference on VLSI, 141-163 (1983)
[14] West, D. B., Parameters of partial orders and graphs: packing, covering and representation, (Rival, I., Graphs and Order (1985), Reidel: Reidel Dordrecht, The Netherlands), 267-350
[15] Yannakakis, M., The complexity of the partial order dimension problem, SIAM J. Algebraic Discrete Methods, 3, 351-358 (1982) · Zbl 0516.06001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.