×

On the structure of trapezoid graphs. (English) Zbl 0849.05060

Consider two parallel lines each containing \(n\) intervals, labelled 1 to \(n\), where two intervals with the same label define a trapezoid with that label. The intersection graph of such a set of trapezoids is called a trapezoid graph. Trapezoid graphs contain both permutation graphs and interval graphs. The paper deals with an operation called vertex splitting which allows to transform a trapezoid graph into a permutation graph with special properties. This implies an \(O(n^3)\) algorithm for recognizing a trapezoid graph. The algorithm is slower than Ma’s algorithm, see T.-H. Ma and J. P. Spinrad [Lect. Notes Comput. Sci. 484, 61-71 (1992; Zbl 0768.68162)], put conceptually simpler and easier to code.
Reviewer: G.Gutin (Odense)

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C99 Graph theory

Citations:

Zbl 0768.68162
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), MacMillan: MacMillan New York · Zbl 1134.05001
[3] Cheah, F., A recognition algorithm for II-graphs, (Ph.D Thesis, TR 246/90 (1990), Dept. of Computer Science, Univ. of Toronto) · Zbl 0698.68040
[4] Cogís, O., On the Ferrers dimension of a digraph, Discrete Math., 38, 47-52 (1982) · Zbl 0472.06007
[5] Corneil, D. G.; Kamula, P. A., Extensions of permutation and interval graphs, (Proceedings 18th Southeastern Conference on Combinatorics, Graph Theory and Computing. Proceedings 18th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., 58 (1987)), 267-275 · Zbl 0652.05055
[6] Dagan, I.; Golumbic, M. C.; Pinter, R. Y., Trapezoid graphs and their coloring, Discrete Appl. Math., 21, 35-46 (1988) · Zbl 0658.05067
[7] Doignon, J. P.; Ducamp, A.; Falmagne, J. C., On realizable biorders and the biorder dimension of a relation, J. Math. Psychol., 28, 73-109 (1984) · Zbl 0562.92018
[8] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[9] Habib, M.; Möhring, R. H., Recognition of partial orders with interval dimension two via transitive orientation with side constraints, (Technical report, TR 244/90 (1990), Tu: Tu Berlin) · Zbl 0608.06004
[10] Ma, T. H., Algorithms on special classes of graphs and partially ordered sets, (Ph.D. Thesis (1990), Dept. of Computer Science, Vanderbilt Univ.,: Dept. of Computer Science, Vanderbilt Univ., Nashville, TN)
[11] Ma, T. H.; Spinrad, J. P., Avoiding matrix multiplication, (Möhring, R. H., Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 484 (1991), Springer: Springer Berlin), 61-71 · Zbl 0768.68162
[12] Spinrad, J., On comparability and permutation graphs, SIAM. J. Comput., 14, 658-670 (1985) · Zbl 0568.68051
[13] J.P. Spinrad, Private communications (1990).; J.P. Spinrad, Private communications (1990).
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.