| In 1993, Langley showed that the bounded bitolerance graphs are equivalent to the class of trapezoid graphs. | В 1993 Лэнгли (Langley) показал, что ограниченные битолерантные графы эквивалентны классу трапецеидальных графов. |
| Algorithms for trapezoid graphs should be compared with algorithms for general co-comparability graphs. | Алгоритмы для трапецеидальных графов следует сравнивать с алгоритмами более общих графов косравнимости. |
| Later, using the box representation of trapezoid graphs, Felsner published O (n log n) {\displaystyle {O}(n\log n)} algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique. | Позднее, используя представление трапецеидальных графов прямоугольниками, Фелснер опубликовал алгоритмы поиска хроматического числа, взвешенного независимого множества, кликового покрытия и максимальной взвешенной клики за время О (n log n) {\displaystyle {O}(n\log n)}. |
| Dagan et al. first proposed an O (n k) {\displaystyle {O}(nk)} algorithm for coloring trapezoid graphs, where n is the number of nodes and k is the chromatic number of the graph. | Даган (Dagan) и др. сначала предложили алгоритм раскраски трапецеидальных графов за время O (n k) {\displaystyle {O}(nk)}, где n - это число вершин, а k -хроматическое число графа. |
| The problems of finding maximum cliques and of coloring trapezoid graphs are connected to channel routing problems in VLSI design. | Задачи поиска максимальных клик и раскраски трапецеидальных графов связаны с задачей прокладки проводящих каналов при проектировании интегральных схем. |
| The class of trapezoid graphs properly contains the union of interval and permutation graphs and is equivalent to the incomparability graphs of partially ordered sets having interval order dimension at most two. | Класс трапецеидальных графов содержит интервальные графы и графы перестановок и эквивалентен графам несравнимости частично упорядоченных множеств, имеющих размерность порядка не больше двух. |